C++ 代码

class Solution {
public:
    int trap(vector<int>& height) {
        //这个题是单调递增栈
        stack<int>stk;
        int res=0;
        for(int i=0;i<height.size();i++){
            int last=0;
            while(stk.size()&&height[stk.top()]<=height[i]){
                //这里我们找的是最大的，所以需要弹出来
                int t=stk.top();
                stk.pop();
                res+=(i-t-1)*(height[t]-last);
                last=height[t];
            }
            if(stk.size()){
                res+=(i-stk.top()-1)*(height[i]-last);
            }
            stk.push(i);
        }
        return res;
    }
};