【leetcode题解】单调栈：接雨水

题目参考：42. 接雨水 - 力扣（LeetCode） (leetcode-cn.com)

好多年前用 Python 写过这题，当时好像用的是双指针法过的，现在用单调栈实现一下，在开始之前，先讲讲单调栈：

单调栈是一种数据结构，主体还是栈，不过要求的是栈里的内容是单调递增或者单调递减的，比如：

序号	1	2	3	4	5
值	9	7	6	4	1

这种就是单调栈内可以存的内容，比如我现在输入了：9 7 3 6 2 4 0 1

那么在元素依次插入这个单调栈的时候，如果当前栈的栈首的元素小于了当前要插入的元素，就应当将斩首的元素弹出，知道弹出后的栈的栈首的元素大于等于当前要插入的元素，所以上述样例插入后就会得到下面的结果：

序号	1	2	3	4	5
值	9	7	6	4	1

当然，上面说的是单调递减的单调栈，对于单调递增的单调栈也是同理，这里留一份单调栈的模板

stack<int> st;
//此处一般需要给数组最后添加结束标志符，具体下面例题会有详细讲解
for (遍历这个数组)
{
    if (栈空 || 栈顶元素大于等于当前比较元素)
    {
        入栈;
    }
    else
    {
        while (栈不为空 && 栈顶元素小于当前元素)
        {
            栈顶元素出栈;
            更新结果;
        }
        当前数据入栈;
    }
}

现在我们来关注这个题目：

class Solution {
public:
    int trap(vector<int>& height) {
    int ans = 0;
    stack<int> stk;
    int n = height.size();
    for (int i = 0; i < n; i++) {
        if (stk.empty() || height[stk.top()] >= height[i]) {
        } else {
            while (!stk.empty() && height[stk.top()] < height[i]) {
                int top = stk.top(); stk.pop();
                if (stk.empty()) break;
                int left = stk.top();
                int curWidth = i - left - 1;
                int curHeight = min(height[left], height[i]) - height[top];
                ans += curWidth * curHeight;
            }
        }
        stk.push(i);
    }
    return ans;
    }
};