题解 | #接雨水问题#

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        if (arr == null || arr.length == 0) return 0;

        int lastIdx = arr.length - 2;
        int[] leftMaxes = new int[arr.length];
        for (int i = 1; i <= lastIdx; i++) {
            leftMaxes[i] = Math.max(leftMaxes[i - 1], arr[i - 1]);
        }

        int[] rightMaxes = new int[arr.length];
        for (int i = lastIdx; i >= 1; i--) {
            rightMaxes[i] = Math.max(rightMaxes[i + 1], arr[i + 1]);
        }

        // 遍历每一根柱子，看看每一根柱子上能放多少水
        int water = 0;
        for (int i = 1; i <= lastIdx; i++) {
            // 求出左边最大、右边最大中的较小者
            int min = Math.min(leftMaxes[i], rightMaxes[i]);
            // 说明这根柱子不能放水
            if (min <= arr[i]) continue;
            // 说明这根柱子能放水
            water += min - arr[i];
        }

        return water;
    }
}

解题思路：遍历，求出左右两边最大值，然后取最小的然后减去当前扫描值就是获取的当前扫描值水量。