Neovim-如何使用编辑器的神

模板题-单调栈

https://www.acwing.com/problem/content/832/

单调栈可以求出来数组中第i个数左边第一个比它小的数.

#include <iostream>
#include <stack>

using namespace std;

int main() {

    stack<int> stk;

    int n;
    cin >> n;

    while (n --) {
        int x;
        cin >> x;
        while (stk.size() && stk.top() >= x) stk.pop();
        if (stk.empty()) cout << "-1" << " ";
        else cout << stk.top() << " ";
        stk.push(x);
    }
    return 0;
}

模板题-滑动窗口最大值与最小值

https://www.acwing.com/problem/content/156/

滑动窗口需要考虑两个变量:

• 窗口大小
• 在固定窗口大小之内, 维护的数值是最大/最小值.

代码模板如下:

#include<iostream>
#include <cstring>

using namespace std;

const int N = 1000010;

int hh = 0, tt = -1;

int n, k;
int a[N], q[N];

int main() {

    cin >> n >> k;
    for (int i = 0; i < n; i ++) cin >> a[i];

    for (int i = 0; i < n; i ++) {
          // 滑动窗口前移后, 维护的窗口下标需要更新
        if (i - k + 1 > q[hh]) hh ++;
      // 用当前枚举的a[i]排除掉队列中的较大的值
        while (hh <= tt && a[i] <= a[q[tt]]) tt --;
        q[ ++ tt ] = i;
        if (i - k + 1 >= 0) printf("%d ", a[q[hh]]);
    }

    puts("");
    hh = 0, tt = -1;

    for (int i = 0; i < n; i ++) {
        if (i - k + 1 > q[hh]) hh ++;
        while (hh <= tt && a[i] >= a[q[tt]]) tt --;
        q[ ++ tt] = i;
        if (i - k + 1 >= 0) printf("%d ", a[q[hh]]);
    }

    return 0;
}

LeetCode上相同的模板题: https://leetcode.cn/problems/sliding-window-maximum/

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
         const int N = 100010;
         int hh = 0, tt = -1;
         int q[N];
         vector<int> ans;

         for (int i = 0; i < nums.size(); i ++) {
             if (i - k + 1 > q[hh]) hh ++;
             while (hh <= tt && nums[i] >= nums[q[tt]]) tt --;
             q[ ++ tt] = i;
             if (i - k + 1 >= 0) ans.push_back(nums[q[hh]]);
         }
         return ans;
    }
};

包含min函数的栈

https://www.acwing.com/problem/content/90/

再维护一个专门存最小值的栈即可.

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stk, stk_min;
    MinStack() {

    }

    void push(int x) {
        stk.push(x);
        if (stk_min.size()) x = min(x, stk_min.top());
        stk_min.push(x);
    }

    void pop() {
        stk.pop();
        stk_min.pop();
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        return stk_min.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */