题解 | #接雨水问题#

思路

计算某一个位置处的雨水，就是计算该位置处往左最大高度、往右的最大高度的最小值与当前高度的差

所以思路一就是遍历每一个点，然后求和
但是因为时间复杂度大，所以超时

思路二是使用动态规划，创建两个dp数组，代表下标为i处的左侧的最大值（或右侧的最大值，包括其本身），递推公式就是：当前最大高度 = max(左侧最大高度, 当前高度)

代码

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */

    long long find_max(vector<int>& arr, int start, int end){
        int i = start;
        int max_res = arr[i];
        while(i<=end){
            if(max_res < arr[i]){
                max_res = arr[i];
            }
            i++;
        }
        return max_res;
    }

    long long maxWater(vector<int>& arr) {
        // write code here
        // 方法1，遍历所有的位置，计算该位置处的容积（左右两侧的最小值-当前位置）
        /*
        long long res = 0;
        for(int i = 1; i<arr.size()-1; i++){
            auto max_left = find_max(arr, 0, i);
            auto max_right = find_max(arr, i, arr.size()-1);
            long long cur = min(max_left, max_right) - arr[i];
            res+=cur;
        }

        return res;
        */

        // 动态规划
        // 两个数组，存放当前位置往左、往右的最大值
        vector<int> dp_l(arr.size());
        vector<int> dp_r(arr.size());

        // 初始化
        dp_l[0] = arr[0];
        dp_r[arr.size()-1] = arr[arr.size()-1]
;        
        // 递归方程
        for(int i = i;i<arr.size(); i++){
            dp_l[i] = max(arr[i], dp_l[i-1]);
        }

        for(int j = arr.size()-2; j>=0; j--){
            dp_r[j] = max(arr[j], dp_r[j+1]);
        }

        // 计算每一个位置的容积
        long long sum = 0;
        for(int i = 1; i<arr.size()-1; i++){
            long long cur = min(dp_l[i], dp_r[i]) - arr[i];
            sum+=cur;
        }

        return sum;
    }
};