42. 接雨水

做法

考虑单独一列能生产多少贡献：用左右最大值去接这列的水

\(O(n)\)

Code

class Solution {
    
public:
        int mx[1000000],rx[1000000];
    int trap(vector<int>& height) {
        int n(height.size());
        // int mx(0);
        for(int i=0;i<n;++i){
            if(i==0) mx[i]=height[i];
            else mx[i]=max(mx[i-1],height[i]);
        }
        int ans(0);
        for(int i=n-1;i>=0;--i){
            if(i==n-1) rx[i]=height[i];
            else rx[i]=max(rx[i+1],height[i]);
            ans+=min(rx[i],mx[i])-height[i];
        }
        /*int ans(0);
        for(int i=0;i<n;++i){
            ans+=min(rx[i],mx[i])-height[i];
        }*/
        return ans;
    }
};