题目描述

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

算法1

(单调栈) 时间复杂度 $O(n)$

参考文献 yxc讲解代码

维护一个单调栈，单调递减。当i的高度大于栈顶值时，此时应该计算当前栈顶t和上一个栈顶last的高度差，然后计算面积。当i的高度小于栈顶值时，计算上一个栈顶last_ 和i的高度差，然后计算面积。

C++ 代码

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int res = 0;

        for(int i=0; i<height.size(); ++i){
            int last = 0;
            while(!st.empty() && height[i] >= height[st.top()]){
                int t = st.top();
                st.pop();
                res += (height[t] - last) * (i - t -1);
                last = height[t];
            }
            if(!st.empty()){
                res += (height[i] - last) * (i - st.top() -1);
            }
            st.push(i);
        }
        return res;
    }
};