题解 | #接雨水问题#

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        int maxValue = arr[0];
        int[] dp1 = new int[arr.length];
        //两端点无容积
        dp1[0] = 0;
        dp1[arr.length - 1] = 0;
		//从左到右，仅考虑左板时的最大容积
        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i] >= maxValue){
                maxValue = arr[i];
                dp1[i] = 0;
            }else {
                dp1[i] = maxValue - arr[i];
            }
        }
        //从右到左，仅考虑右板时的最大容积
        //每个位置二者的最小值即是当前位置的最大容量
        maxValue = arr[arr.length - 1];
        for (int i = arr.length - 2; i > 0; i--){
            if (arr[i] >= maxValue){
                maxValue = arr[i];
                dp1[i] = 0;
            }else {
                dp1[i] = Math.min(maxValue - arr[i], dp1[i]);
            }
        }
        return Arrays.stream(dp1).sum();
    }
}