单调栈

单调栈是一种和单调队列类似的数据结构。单调队列主要用于 解决滑动窗口问题，单调栈则主要用于 解决NGE问题（Next Greater Element），也就是，对序列中每个元素，找到下一个比它大的元素。（当然，“下一个”可以换成“上一个”，“比它大”也可以换成“比他小”，原理不变。）

我们维护一个栈，表示“待确定NGE的元素”，然后遍历序列。当我们碰上一个新元素，我们知道，越靠近栈顶的元素离新元素位置越近。所以不断比较新元素与栈顶，如果新元素比栈顶大，则可断定新元素就是栈顶的NGE，于是弹出栈顶并继续比较。直到新元素不比栈顶大，再将新元素压入栈。显然，这样形成的栈是单调递减的。

#include<bits/stdc++.h>
using namespace std;
int stk[100005];
int h[100005];
int l[1000005];
int main() {
    int n;
    cin >> n;
    for(int i = 1;i <= n; ++ i) {
        cin >> h[i];    
    }
    h[0] = -1;
    int tt = 0;
    for(int i  = 1;i <= n; ++ i) {
        while(h[stk[tt]] >= h[i]) tt --; //本例中为单调递增
        l[i] = stk[tt];
        stk[++ tt] = i;    
    }
    for(int i = 1;i <= n; ++ i) {
        cout << l[i] << " ";    
    }
}

例题leetcode-42接雨水

思路：利用单调栈的求解过程，在运用单调栈的时候，遇见高的柱子就会形成接雨水的凹槽，那么对于每次单调栈的出栈，我们就可以进行处理，即计算每次出栈时出栈柱子上方可以存储的雨水。

class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        stack<int> st;
        for(int i = 0;i < height.size(); ++ i) {
            while(!st.empty() && height[st.top()] < height[i]) {
                int cur = st.top();//记录当前可存储水的底部高度。
                st.pop();
                if(st.empty()) break;
                int l = st.top();//存水的左端
                int r = i;//存水的右端
                res += (min(height[l],height[r]) - height[cur]) * (r - l - 1);//计算存水的量
            }
            st.push(i);
        }
        return res;
    }
};