题解 | #容器盛水问题#

对于每一个位置i，它上方所能容纳的水的容量等于：

Max{Min{i位置左侧的最大值，i位置右侧的最大值}-arr[i],0}

​ 而整个容器所能容纳的水的容量就为每一个位置上所能容纳的水的容量之和，第一个位置和最后一个位置上方所能容纳的水的容量为0。

​ 为此，要求两个辅助数组leftMax和rightMax。leftMax[i]表示arr[0..i-1]中的最大值，rightMax[i]表示arr[i+1,arr.length-1]中的最大值。

public long maxWater (int[] arr){

    if (arr == null || arr.length <= 2){
        return 0;
    }

    int n = arr.length;
    // leftMax[i]表示arr[i]左侧的最大值
    // rightMax[i]表示arr[i]右侧的最大值
    long[] leftMax = new long[n];
    long[] rightMax = new long[n];

    long left = arr[0];
    long right = arr[n-1];
    for (int i = 1; i < n; i++) {

        left = left >= arr[i-1] ? left : arr[i-1];
        leftMax[i] = left;
    }

    for (int i = n-2; i > 0; i--) {

        right = right >= arr[i+1] ? right : arr[i+1];
        rightMax[i] = right;
    }

    long res = 0;

    // 容器盛水的容量等于，对于每一个位置i的上方的容量之和，那么每一个位置上方的水容量为：
    // Max{Min{i位置左侧的最大值，i位置右侧的最大值}-arr[i],0}
    for (int i = 1; i < n - 1; i++) {
        res += Math.max(Math.min(leftMax[i],rightMax[i])-arr[i],0);
    }

    return res;
}

优化一下空间复杂度，将其由上面的O(n)变为O(1)：

​ 设定左右两个指针i和j，初始值设置为1和n-2；然后再设置两个辅助变量leftMax和rightMax，分别表示i左侧的最大值和j右侧的最大值。那么求解的过程就是：

​ 如果leftMax<=rightMax，那么说明i位置的右侧的最大值一定不会小于rightMax，那么决定i位置处水容量大小的决定因素就是rightMax了，所以此时可以求解i位置容纳的水量：
Max{leftMax - arr[i],0}
然后更新leftMax，L向右移动：

leftMax = leftMax >= arr[i] ? leftMax : arr[i];
​ 对于leftMax>rightMax，也是同样的道理，说明R位置左侧的最大值一定不会小于leftMax，那么决定j位置处的水容量的大小的决定因素就是leftMax了，所以此时可以求解j位置的水量：

Max(rightMax-arr[j],0)
​ 然后更新rightMax，j向左移动：

rightMax = rightMax >= arr[j] ? rightMax : arr[j];
​ 最终的结果就是将i和j位置上的容量相加起来的结果。

    public long maxWater (int[] arr) {
        if(arr == null || arr.length <= 2)return 0;
        long res = 0;
        int n = arr.length;
        int leftMax = arr[0],rightMax = arr[n - 1];
        int i = 1,j = n - 2;
        while(i &lt;= j){
            if(leftMax &lt;= rightMax){
                res += Math.max(leftMax - arr[i],0);
                leftMax = leftMax &gt;= arr[i] ? leftMax : arr[i];
                i++;
            } else {
                res += Math.max(rightMax - arr[j],0);
                rightMax = rightMax &gt;= arr[j] ? rightMax : arr[j];
                j--;
            }
        }
        return res;
    }