题解 | #接雨水问题#

发现规律：如果数组两端恰好是“杯壁”，即数组两端的值是第一和第二大的，那么

雨水的面积 = 以数组长度为底且以最长杯壁为高的矩形面积 - 墙壁面积 - 空白面积;

其中，

以数组长度为底且以最长杯壁为高的矩形面积 = 第一大的值 * (|第一大的值的下标 - 第二大的值的下标| + 1);

墙壁面积，即数组元素的和，可以累加计算得出，在遍历数组的时候就可以顺便累加;

空白面积 = (第一大的值 - 第二大的值) * (|第一大的值的下标 - 第二大的值的下标|)。

因此，得到一个解题思路——尽可能地找“杯壁”。

注意事项：使用Java语言，还要注意两个int类型相乘可能会溢出，导致计算结果不正确，因此一定要注意用适当的方法转换成long类型的乘法。

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        if (arr == null || arr.length <= 2) return 0;
        //找到最大值，以最大值为边界，求两段数组的雨水量之和。
        int maxIndex = findMaxIndex(arr);
        long leftRes = LeftMaxWater(arr,0,maxIndex);
        long rightRes = rightMaxWater(arr,maxIndex,arr.length - 1);

        return leftRes + rightRes;
    }

    private long rightMaxWater(int[] a, int s, int e) {
        if (e - s <= 1) return 0;
        //反转之后，使用LeftMaxWater
        int i = s, j = e;
        while (i < j){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            ++i;
            --j;
        }

        return LeftMaxWater(a,s,e);
    }

    private long LeftMaxWater(int[] a, int s, int e) {
        if (e - s <= 1) return 0;
        int firstMaxIndex = s;

        long res = 0;
        long currTotalWall = a[s];
        for (int i = s + 1; i <= e; i++) {
            currTotalWall += a[i];

            if (a[i] >= a[firstMaxIndex]){
                long blank = (i - firstMaxIndex + 0L) * (a[i] - a[firstMaxIndex]);

                res += (i - firstMaxIndex + 1L) * a[i] - blank - currTotalWall;

                firstMaxIndex = i;
                currTotalWall = a[i];
            }
        }

        return res;
    }

    private int findMaxIndex(int[] a) {
        int r = 0;
        for (int i = 1; i < a.length; i++) {
            if (a[r] < a[i]){
                r = i;
            }
        }
        return r;
    }
}