题解 | #接雨水问题#

双指针法：除了第一列与最后一列不接雨水，计算其他每一列能接到的雨水，第i列能接到的雨水=min(i左边的最高值，i右边的最高值) – 第i列本身的高度。O(n^2)可能会超时。

动态规划：递推的计算两个数组，left_max保存左边最高的高度，right_max保存右边最高的高度。第i列能接到的雨水=min(left_max[i], right_max[i]) – height[i]。一下为动态规划代码。

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        if(arr.size()<=2) return 0;
        int n=arr.size();
        vector<int> left_max(n,0);
        left_max[0]=arr[0];
        for(int i=1;i<n;i++) left_max[i]=max(arr[i],left_max[i-1]);
        vector<int> right_max(n,0);
        right_max[n-1]=arr[n-1];
        for(int i=n-2;i>=0;i--) right_max[i]=max(arr[i],right_max[i+1]);
        long long sum=0;
        for(int i=0;i<n;i++){
            int h=min(left_max[i],right_max[i])-arr[i];
            if(h>0) sum+=h;
        }
        return sum;
    }
};