LeetCode Hot 100 刷题记录 05：盛最多水的容器

题目链接

11. 盛最多水的容器

解题思路

初始时将两个指针放在数组两端，此时容器宽度最大。当前容积由宽度与两侧较短高度共同决定：

容积 = (right - left) × min(height[left], height[right])

计算当前容积后，移动高度较短的一侧。因为宽度一定会缩小，保留较短边无法突破当前高度瓶颈；只有移动较短边，才可能遇到更高的边界并得到更大容积。

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

Java 解答

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int left = 0;
        int right = height.length - 1;
        
        while (left < right) {
            max = Math.max(max, (right - left) * Math.min(height[left], height[right]));
            if (height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return max;
    }
}

复盘

暴力枚举所有左右边界需要 O(n²)。双指针每次排除不可能产生更优结果的一侧，在不遗漏最优解的前提下，将搜索过程压缩为一次线性扫描。