题解 | #接雨水问题#

看起来是上升（非严格）子序列和下降子序列问题。不过直接暴力。

例如，输入[3,1,2,5,2,4]

填满雨水后变成 [3, 3, 3, 5, 4, 4]

所以只要找到最大值，最大值左边都非下降，右边的非上升。

if(arr[i]<arr[i-1]){  // 左边
  res += (arr[i-1]-arr[i]);
  arr[i] = arr[i-1];
}

....

if(arr[i]<arr[i+1]){  // 右边
	res += (arr[i+1]-arr[i]);
	arr[i] = arr[i+1];
}

注意答案要用long long 完整代码：

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        if(arr.size()<=1) return 0;
        long long maxx, pos;
        maxx = -1; pos = -1;
        // 找最大值和其所在的索引
        for(int i=0; i<arr.size(); i++){
            if(arr[i]>maxx){
                maxx = arr[i];
                pos = i;
            }
        }
        long long res = 0;
        // 在pos左边应该是上升子序列，右边是下降子序列
        for(int i=1; i<pos; i++){
            if(arr[i]<arr[i-1]){
                res += (arr[i-1]-arr[i]);
                arr[i] = arr[i-1];
            }
        }
        for(int i=arr.size()-2; i>pos; i--){
            if(arr[i]<arr[i+1]){
                res += (arr[i+1]-arr[i]);
                arr[i] = arr[i+1];
            }
        }
        return res;
    }
};

结果：