42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

单调栈

• 维护一个stk（单调递减，栈顶元素最小），存储的是数组的下标。
• 当接雨水区域存在时，说明遍历到的元素num要严格大于栈顶元素。
• 弹出栈顶元素时，下一个栈顶元素代表的是左边界。
• 细节在于，底与高的选取，宽度的选取只要左右边界下标相减。
• 逐个更新，即每次弹出的首个元素，作为可选择的底，下一个栈顶元素作为可能的左边界。

class Solution {
public:
    int trap(vector<int>& height) {
        // stack
        // 单调栈，递减，栈顶的元素是最小的
        // 若遍历到的元素比栈顶大，说明遇到右边界，出栈比较
        stack<int> stk;
        int ans = 0;
        for(int i = 0; i < height.size(); ++i){
            while(!stk.empty() && height[stk.top()] < height[i]){
                int curtop = 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[curtop];
                ans += curheight*curwidth;
            }
            stk.push(i);
        }
        return ans;
    }
};

原文：https://www.cnblogs.com/alyosha/p/14688659.html