题解 | #容器盛水问题#

/*方法1       时间复杂度O(N^2)
    i位置上方的水= max{min{i左侧最大值，i右侧最大值}-arr[i],0}
    * */
    public static int getWater1(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int res = 0;
        for (int i = 1; i < arr.length - 1; i++) {
            int leftMax = 0;
            int rightMax = 0;
            for (int j = 0; j < i; j++) {
                leftMax = Math.max(arr[j], leftMax);
            }
            for (int j = i + 1; j < arr.length; j++) {
                rightMax = Math.max(arr[j], rightMax);
            }

            res += Math.max(Math.min(leftMax, rightMax) - arr[i], 0);
        }
        return res;
    }

    /*方法2：把左右侧最大值存起来
    时间复杂度O(N)   空间复杂度O(N)
    * */
    public static int getWater2(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }

        int[] leftMaxs = new int[arr.length];
        leftMaxs[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            leftMaxs[i] = Math.max(leftMaxs[i - 1], arr[i]);
        }
        int[] rightMaxs = new int[arr.length];
        rightMaxs[arr.length - 1] = arr[arr.length - 1];
        for (int i = arr.length - 2; i >= 0; i--) {
            rightMaxs[i] = Math.max(rightMaxs[i + 1], arr[i]);
        }

        int res = 0;
        for (int i = 1; i < arr.length - 1; i++) {
            res += Math.max(Math.min(leftMaxs[i - 1], rightMaxs[i + 1]) - arr[i], 0);
        }
        return res;
    }

    /*方法3：时间复杂度O(N)     空间复杂度O(1)
    左右指针L   R
    leftMax表示[0...L-1]中的最大值     rightMax表示[R+1....N-1]中的最大值
    * */
    public static int getWater3(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int res = 0;
        int leftMax = arr[0];
        int rightMax = arr[arr.length - 1];
        int L=1;
        int R=arr.length-2;
        while (L<=R){
            if(leftMax<=rightMax){
                res+=Math.max(0,leftMax-arr[L]);
                leftMax=Math.max(leftMax,arr[L]);
                L++;
            }else {
                res+=Math.max(0,rightMax-arr[R]);
                rightMax=Math.max(rightMax,arr[R]);
                R--;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[] nums=new int[n];
        for (int i = 0; i <n ; i++) {
            nums[i]=in.nextInt();
        }

        int res=getWater3(nums);
        System.out.println(res);
    }