题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

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

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

解法

解法一 暴力解法

嵌套两个for循环暴力求解

class Solution {
    public int maxArea(int[] height) {
        // O(N^2)穷举法
        int maxArea = 0;
        for(int i = 0; i < height.length - 1; i++) {
            for(int j = i + 1; j < height.length; j++) {
                int minHeight = Math.min(height[i], height[j]);
                int area = (j - i) * minHeight;
                maxArea = Math.max(area, maxArea);
            }
        }
        return maxArea;
    }
}

时间复杂度为O(N2)，很low，超出时间限制

优化 – 找出可优化遍历省略

class Solution {
    public int maxArea(int[] height) {
        // O(N^2)穷举法
        int maxArea = 0;
        int maxHeightLeft = 0;
        for(int i = 0; i < height.length - 1; i++) {
            // 将高宽都变短的情况优化掉
            if (maxHeightLeft >= height[i]) continue;
            maxHeightLeft = height[i];
            for(int j = i + 1; j < height.length; j++) {
                int minHeight = Math.min(height[i], height[j]);
                int area = (j - i) * minHeight;
                maxArea = Math.max(area, maxArea);
            }
        }
        return maxArea;
    }
}

优化掉了大量遍历操作，不会有超时实例，但是解法本质不变，时间复杂度仍然是O(N2).

解法二 双指针法

• 两个指针从两边向内收缩，如果长板向内收缩，不管里面的板是变长还是变短，因为短板限制了容量的增加，宽度又变短，容量不可能增加。
• 因此，要想遍历到更大的容量，在宽度减少的情况下，只能让短板变高。

class Solution {
    public int maxArea(int[] height) {
        // 移动长板，面积不可能增大，所以每次移动短板，直到相撞
        int maxArea = 0, left = 0, right = height.length - 1;
        while (left < right) {
            int currentArea = 0;
            if (height[left] < height[right]) {
                currentArea = height[left] * (right - left);
                maxArea = Math.max(currentArea, maxArea);
                // 移动左板
                left++;
            } else {
                currentArea = height[right] * (right - left);
                maxArea = Math.max(currentArea, maxArea);
                // 移动右板
                right--;
            }
        }
        return maxArea;
    }
}

时间复杂度：O(N)!

继续优化

短板向内缩减时，如果里面的板比原本的短板更短，就没必要进行这轮的比较

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int left = 0;
        int right = height.length - 1;
        while (left != right) {
            if (height[left] <= height[right]) {
                // 左边短
                int shortHeight = height[left];
                maxArea = Math.max(maxArea, (right - left) * shortHeight);
                left++;
                while (height[left] < shortHeight && left != right) left++;
            } else {
                // 左边长
                int shortHeight = height[right];
                maxArea = Math.max(maxArea, (right - left) * shortHeight);
                right--;
                while (height[right] < shortHeight && left != right) right--;
            }
        }
        return maxArea;
    }
}