《leetcode42接雨水》

去考虑每个块的贡献，那么就会发现，每个块贡献的雨水，就是min(左边最高的，右边最高的)-它的高度。

但是统计这个水，暴力的话大概就要N^2了。所以我们考虑去高效地统计。

dp统计一下就行了，正反扫两遍O（n）

class Solution {
public:
    int trap(vector<int>& height) {
        int N = 1e5+5,len = height.size();
        int dp[N][2],ans = 0;//左,右
        memset(dp,0,sizeof(dp));
        for(int i = 1;i < len-1;++i) 
        {
            dp[i][0] = dp[i-1][0] > height[i-1] ? dp[i-1][0] : height[i-1];
        }
        for(int i = len-2;i >= 1;--i)
        {
            dp[i][1] = dp[i+1][1] > height[i+1] ? dp[i+1][1] : height[i+1];
        }
        for(int i = 1;i < len-1;++i)
        {
            int ma = min(dp[i][0],dp[i][1]);
            if(ma <= height[i]) continue;
            ans += ma-height[i];
        }
        return ans;
    }
};

第二种思路：单调栈。

我们维护一个单调递减栈，计算横向距离。所以这里找的就是左边第一个比它大的，和右边第一个比它大的。

中间可能同高度的距离就会合并。和上一题差不多的写法。

class Solution {
public:
    int trap(vector<int>& height) {
        typedef long long LL;
        int N = 1e5+5,len = height.size();
        int S[N],top = 0;
        LL ans = 0;
        for(int i = 0;i < len;++i)
        {
            while(top != 0 && height[i] > height[S[top]])
            {
                LL dis = i-S[top-1]-1;
                if(top != 1) ans += dis*(min(height[i],height[S[top-1]])-height[S[top]]);
                top--;
            }
            S[++top] = i;
        }
        return ans;
    }
};