题解 | #接雨水问题#

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        if(arr.length<=2) return 0;
        // arr :3 1 2 5 2 4
        // lMax:3 3 3 5 5 5
        // rMax:5 5 5 5 4 4
        // max :3 3 3 5 4 4
        // size:0 2 1 0 2 0
        int[] lMax = new int[arr.length]; // 左侧最大高度
        int[] rMax = new int[arr.length]; // 右侧最大高度
        int[] max = new int[arr.length]; // 两侧最大高度
        int[] size = new int[arr.length]; // 可乘的容量

        // 计算左侧最大高度
        int curLMax = arr[0];
        for (int i = 0; i < arr.length; i++) {
            curLMax = Math.max(arr[i], curLMax);
            lMax[i] = curLMax;
        }

        // 计算右侧最大高度
        int curRMax = arr[arr.length-1];
        for (int i = arr.length-1; i >=0; i--) {
            curRMax = Math.max(arr[i], curRMax);
            rMax[i] = curRMax;
        }

        // 计算两侧最大高度
        for (int i = 0; i < arr.length; i++) {
            max[i] = Math.min(lMax[i], rMax[i]);
        }

        // 计算可乘的容量
        for (int i = 0; i < arr.length; i++) {
            size[i] = max[i] - arr[i];
        }

        // 汇总可乘的容量
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += size[i];
        }
        
        return sum;
    }
}