Problem:42. 接雨水

思路：单调栈记录一个递减序列，找当前元素左边的比他大的第一个数过程累加答案。

Accode:

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

其实那判断部分完全可以去除。

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> sta;
        int ans = 0;
        for (int i = 0; i < height.size(); i++) {
            while (sta.size() > 0 && height[sta.top()] <= height[i]) {
                int top = sta.top();
                sta.pop();
                if (sta.size() == 0)
                    break;
                int width = i - sta.top() - 1;
                ans +=
                    width * (min(height[i], height[sta.top()]) - height[top]);
            }
            sta.push(i);
        }
        return ans;
    }
};

时间复杂度：$o(n)$