LeetCode - 11.盛最多水的容器.java

原题链接：https://leetcode-cn.com/problems/container-with-most-water/

说明：
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49

/*
 * @lc app=leetcode.cn id=11 lang=java
 *
 * [11] 盛最多水的容器
 */

// @lc code=start
class Solution {
    /**
     * 暴力解法
     * 两次循环得到所有的结果，然后返回最大值
     * 时间复杂度O(n^2)
     * 空间复杂度O(1)
     */
    // public int maxArea(int[] height) {
    //     int max = 0;
    //     for(int i = 0; i < height.length; i++) {
    //         for(int j = i+1; j < height.length; j++) {
    //             int tempMax = (j - i) * Math.min(height[i], height[j]);
    //             max = Math.max(tempMax, max);
    //         }
    //     }
    //     return max;
    // }
    /**
     * 双指针
     * 头部和尾部向中间移动， 每次判断头部和尾部的值，哪个小，哪个向中间移动
     * 官方题解：https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/
     * 
     * 时间复杂度O(n)
     * 空间复杂度O(1)
     * 
     * 执行用时：4 ms, 在所有 Java 提交中击败了67.78%的用户
     * 内存消耗：39.9 MB, 在所有 Java 提交中击败了83.04%的用户
     */
    // public int maxArea(int[] height) {
    //     int length = height.length;
    //     int max = 0;
    //     int j = length - 1;
    //     int i = 0;
    //     while(j > i) {
    //         int tempMax = (j - i) * Math.min(height[i], height[j]);
    //         max = Math.max(tempMax, max);
    //         if(height[i] > height[j]) {
    //             j--;
    //         } else {
    //             i++;
    //         }
    //     }
    //     return max;
    // }

    /**
     * 双指针
     * 在上面解法的基础上进行优化，执行用时缩短
     * 
     * 时间复杂度O(n)
     * 空间复杂度O(1)
     * 
     * 执行结果：通过
     * 执行用时：2 ms, 在所有 Java 提交中击败了99.16%的用户
     * 内存消耗：39.9 MB, 在所有 Java 提交中击败了84.48%的用户
     */
    // public int maxArea(int[] height) {
    //     int max = 0;
    //     int tempMax = 0;
    //     int j = height.length - 1;
    //     int i = 0;
    //     while(j > i) {
    //         /**
    //          * 既然有 height[i] > height[j]判断，就将tempMax的计算放到了具体的判断里面，避免了一次 Math.min 的操作
    //          */
    //         if(height[i] > height[j]) {
    //             tempMax = (j - i) * height[j];
    //             // max = Math.max(tempMax, max);
    //             // 使用上面代码，执行时间会增加 1 ms
    //             max = max > tempMax ? max : tempMax;
    //             j--;
    //         } else {
    //             tempMax = (j - i) * height[i];
    //             max = max > tempMax ? max : tempMax;
    //             i++;
    //         }
    //     }
    //     return max;
    // }


    public int maxArea(int[] height) {
        int max = 0;
        int right = height.length - 1;
        int left = 0;
        while(left < right) {
            int rightHeight = height[right];
            int leftHeight = height[left];
            int minHeight = Math.min(leftHeight, rightHeight);
            int tempMax = (right - left) * minHeight;
            if(tempMax > max) max = tempMax;
            if(height[left] < height[right]) {
                // 左边高度一直小于最小高度时，直接向中间靠拢，无需再计算面积
                while(left < right) {
                    leftHeight = height[left];
                    if(leftHeight <= minHeight)
                        left++;
                    else
                        break;
                }
            } else {
                while(left < right) {
                    // 右边高度一直小于最小高度，向中间靠拢，无需计算面积
                    rightHeight = height[right];
                    if(rightHeight <= minHeight)
                        right--;
                    else
                        break;
                }
            }
        }
        return max;
    }
}
// @lc code=end

github：https://github.com/huxq-coder/LeetCode