009-盛最多水的容器（双指针）

盛最多水的容器

问题描述

给定一个长度为 n 的非负整数数组 height，其中 height[i] 表示第 i 条垂直线的高度。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

注意：你不能倾斜容器。

示例

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水的最大值为 49（即选择第2个和第9个柱子）。

解决思路

方法：双指针法

1. 初始化：使用两个指针，一个在数组的开头（left），一个在数组的末尾（right）
2. 计算当前面积：面积 = min(height[left], height[right]) * (right - left)
3. 移动指针：移动高度较小的指针（因为移动较高的指针不可能得到更大的面积）
4. 更新最大面积：每次计算后比较并保存最大值
5. 终止条件：当 left 和 right 相遇时停止

为什么这个方法有效？

• 贪心选择：每次移动较短的边，保留了可能产生更大面积的机会
• 完备性：通过双指针的移动，我们检查了所有可能的容器组合
• 高效性：只需要一次线性扫描，时间复杂度为 O(n)

JavaScript实现

function maxArea(height) {
    let max = 0;
    let left = 0;
    let right = height.length - 1;
    
    while (left < right) {
        // 计算当前面积
        const currentArea = Math.min(height[left], height[right]) * (right - left);
        // 更新最大面积
        max = Math.max(max, currentArea);
        // 移动指针
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return max;
}

示例解析

以输入 [1,8,6,2,5,4,8,3,7] 为例：

初始状态：
left=0 (height=1), right=8 (height=7)
面积=min(1,7)*8=8
max=8
移动left（因为height[left]较小）

下一步：
left=1 (height=8), right=8 (height=7)
面积=min(8,7)*7=49
max=49
移动right（因为height[right]较小）

下一步：
left=1 (height=8), right=7 (height=3)
面积=min(8,3)*6=18
max保持49
移动right

...（继续此过程直到left >= right）

复杂度分析

• 时间复杂度：O(n)，只需一次扫描
• 空间复杂度：O(1)，只使用了常数个额外空间

边界情况考虑

1. 空数组或单元素数组：返回0（无法形成容器）
2. 所有高度相同：最大面积为 height[0] * (n-1)
3. 高度为0：0高度不会影响计算（因为面积由较短的边决定）

可视化示例

高度图：
8|       ■       ■
7|       ■       ■   ■
6|   ■   ■       ■   ■
5|   ■   ■   ■   ■   ■
4|   ■   ■   ■   ■   ■
3|   ■   ■   ■   ■   ■   ■
2|   ■   ■   ■   ■   ■   ■
1|■  ■   ■   ■   ■   ■   ■
 0 1 2 3 4 5 6 7 8 9

最大面积容器：
左边界：第2个柱子（height=8）
右边界：第9个柱子（height=7）
宽度：7（9-2）
高度：min(8,7)=7
面积：7*7=49

总结

盛水容器问题的双指针解法：

1. 简单高效，时间复杂度为线性
2. 关键在于理解为什么移动较短的指针是正确的
3. 适用于各种边界情况
4. 是双指针技巧的经典应用场景