题解 | #接雨水问题#

动态规划 计算每一个位置左右最大值

根据这个位置左右最大值 ， 可以计算这个位置接水量

public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        int n  = arr.length;
        if (n == 0){
            return 0;
        }
        int[] leftMaxDp = new int[n];
       leftMaxDp[0] = arr[0];
        for(int i= 1;i<n;i++){
            leftMaxDp[i] = Math.max(leftMaxDp[i-1],arr[i]);
        }
        
        int[] rightMaxDp = new int[n];
        rightMaxDp[n-1] = arr[n-1];
        for(int i = n-2;i>=0;i--){
            rightMaxDp[i] = Math.max(rightMaxDp[i+1],arr[i]);
        }
        long res = 0;
//         计算每一个位置接水量
        for(int i =1;i<n-1;i++){
            int temp = Math.min(leftMaxDp[i],rightMaxDp[i]) - arr[i];
            res += temp;
        }
         return res;
    }
}