代码随想录 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 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

解题思路
本题解法很多，如动态规划，单调栈，双指针。本文只介绍单调栈的解法。
雨水的面积可以横向计算，也可纵向计算。单调栈比较适合横向计算。需要找出每一层的可接雨水的面积，即需要找出元素i左右的最近一个比i高的柱子。用单调栈st来记录柱子的索引值，如果当前的i的柱子高度小于st栈顶的柱子，则把i压入栈中；如果当前i的柱子高度和st栈顶的柱子高度相等，则替换栈顶元素。如果当前的i的柱子高度大于st栈顶的柱子，则说明横向计算可接雨水区域的高h和宽w，这里的思路和739.每日温度，496.下一个更大元素相似。最后返回sum值。

代码实现

class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0;
        stack<int> st;
        st.push(0);
        for (int i=1;i<height.size();i++) {
            if (height[i] < height[st.top()]) {
                st.push(i);
            } else if (height[i]==height[st.top()]) {
                st.pop();
                st.push(i);
            } else {
                while (!st.empty() && height[i] > height[st.top()]) {
                    int mid = st.top() ;
                    st.pop();
                    if (!st.empty()) {
                        int h = min(height[i],height[st.top()]) - height[mid];
                        int w = i - st.top() - 1;
                        sum += h * w;
                    }    
                }
                st.push(i);
            }
        }
        return sum;
    }
};