42. 接雨水

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

解法一：Brute-Force, TLE

寻找左边最大值和右边最大值，取其小

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size(),ans=0;
        auto startit=cbegin(height), endit=cend(height);
        for(int i=0;i<n;i++){
            int l=*max_element(startit,startit+i+1);
            int r=*max_element(startit+i, endit);
            ans+=min(l,r)-height[i];
        }
        return ans;
    }
};

解法二 动态规划

避免解法一的多次运算左边最大和右边最大值

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size(),ans=0;
        vector<int> leftMax(height.size(),0),rightMax(height.size(),0);
        for(int i=0;i<n;i++){
            leftMax[i]=i==0?height[i]:max(leftMax[i-1],height[i]);
        }
        for(int i=n-1;i>=0;i--){
            rightMax[i]=i==n-1?height[i]:max(rightMax[i+1],height[i]);
        }
        for(int i=0;i<n;i++){
            ans+=min(leftMax[i],rightMax[i])-height[i];
        }
        return ans;
    }
};

解法三 双指针

原理同解法二，但因为从左至右和从右至左都是单调递增趋势（要找最大），所以可以使用双指针去解。

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        if(n==0) return 0;
        int l=0,r=n-1,max_l=height[l],max_r=height[r],ans=0;
        while(l<r){
            if(max_l<max_r){
                ans+=max_l-height[l];
                max_l=max(max_l,height[++l]);
            }else{
                ans+=max_r-height[r];
                max_r=max(max_r,height[--r]);
            }
        }
        return ans;
    }
};