NC128：容器盛水问题

依次求出数组中每一个位置上方的水，累加起来就是答案
解法一：暴力 // 超时

public long maxWater (int[] arr) {
        if(arr==null || arr.length<3){
            return 0;
        }
        int maxwater=0;
        //0位置和n-1位置上方一定没有水，故不用尝试
        for(int i=1;i<arr.length-1;i++){
            int leftmax=0,rightmax=0;
            //遍历求i左侧的最大值
            for(int j=0;j<i;j++){
                leftmax= leftmax<arr[j] ? arr[j] : leftmax;
            }
            //遍历求i右侧的最大值
            for(int k=i+1;k<arr.length;k++){
                rightmax= rightmax<arr[k] ? arr[k] : rightmax;
            }
            maxwater=maxwater+Math.max(0,Math.min(leftmax,rightmax)-arr[i]);
        }
        return maxwater;
    }

解法二：空间换时间
思路： 先构建左右最大值数组(这里用long防止溢出）

    public long maxWater (int[] arr) {
        // write code here
        if(arr==null || arr.length<3){
            return 0;
        }
        long maxwater=0;
        long[] leftmax=new long[arr.length];
        long[] rightmax=new long[arr.length];
        leftmax[0]=arr[0];
        rightmax[arr.length-1]=arr[arr.length-1];
        for(int i=1;i<arr.length;i++){
            leftmax[i]=Math.max(leftmax[i-1],arr[i]);
        }
        for(int i=arr.length-2;i>=0;i--){
            rightmax[i]=Math.max(rightmax[i+1],arr[i]);
        }
        for(int i=1;i<arr.length-1;i++){
            maxwater=maxwater+Math.max(Math.min(leftmax[i-1],rightmax[i+1])-arr[i],0);
        }
        return maxwater;
    }

解法三：双指针法
基本思路就是将arr(left, right)内的总容积，通过每次移除一个边界元素的方式逐步计算出来，也就是：
s(arr, left, right) = x1 + s(arr, left+1, right)，1) 或者：
s(arr, left, right) = x2 + s(arr, left, right-1)，2)
假设arr[left] < arr[right]，那么具体用1)还是2)呢，也就是应该移除left，还是right呢？
1 如果移除小的那个，我们可以保证：max(arr[left], arr[right]) >= set(已移除左元素）
当再移除arr[left]时，显然可以立刻得到left上能容纳的最大容量，如下：
min(max(set(已移除左元素)), arr[right]) - arr[left] = max(set(已移除左元素) - arr[left]
而这个已移除左元素的max值，我们只需要使用一个lmax记录就可以了。
2 如果移除大的那个，我们在移除的时间点无法确定它能容纳的最大容量，因为我们无法确定剩余元素的最小值。
这样通过逐步移除较小的那个边界元素，我们就可以计算出最终的容量。

    public long maxWater (int[] arr) {
        // write code here
        if(arr==null||arr.length<3) return 0;
        long leftmax = arr[0];
        long rightmax = arr[arr.length-1];
        int l = 1;
        int r = arr.length-2;
        long volume = 0;
        while(l<=r){
            if(leftmax<=rightmax){
                volume += Math.max(leftmax-arr[l],0);
                leftmax = Math.max(leftmax,arr[l++]);
            }else{
                volume += Math.max(rightmax-arr[r],0);
                rightmax = Math.max(rightmax,arr[r--]);
            }
        }
        return volume;
    }