单调栈与单调队列

不管是单调栈还是单调队列，都有金字塔形状和倒金字塔形状，按照具体题意分析；

单调栈

问题类型：

在数组里面找到下一个比当前元素大的元素数值或下标、接雨水等等；

• 栈里面可以存下标或数值，建议存下标；
• 单调栈分为金字塔形状和倒金字塔形状；
• 按遍历方向不同，有不同的实现方式；

样式代码

// 从后往前遍历
vector<int> nextGreaterElementCore(vector<int>& nums) {
    int n = nums.size();
    stack<int> st;
    vector<int> ans(n, -1);
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && st.top() <= nums[i]) {
            st.pop();
        }
        ans[i] = st.empty() ? -1 : st.top();
        st.push(nums[i]);
    }
    return ans;
}

// 从前往后遍历
vector<int> dailyTemperatures(vector<int>& T) {
    stack<int> st; // 递增栈
    vector<int> result(T.size(), 0);
    for (int i = 0; i < T.size(); i++) {
        while (!st.empty() && T[i] > T[st.top()]) { // 注意栈不能为空
            result[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);

    }
    return result;
}


// 遇到循环数组时
for (int i = 2 * n - 1; i >= 0; --i) {
    int curIndex = i % n;
    ...
}

单调队列

样式代码

• 从front到back单调递减；
• que.pop(滑动窗口中移除元素的数值)
• que.push(滑动窗口添加元素的数值)
• que.front()就返回我们要的最大值

class MyQueue { //单调队列（从大到小）
public:
    deque<int> que; // 使用deque来实现单调队列
    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    // 同时pop之前判断队列当前是否为空。
    void pop(int value) {
        if (!que.empty() && value == que.front()) {
            que.pop_front();
        }
    }
    // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，
    // 直到push的数值小于等于队列入口元素的数值为止。
    // 这样就保持了队列里的数值是单调从大到小的了。
    void push(int value) {
        while (!que.empty() && value > que.back()) {
            que.pop_back();
        }
        que.push_back(value);
    }
    // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    int front() {
        return que.front();
    }
};

【参考资料】代码随想录、力扣