好的，我们这次来详细讲解 LeetCode 第 11 题「盛最多水的容器」。

1. 题目描述

给你一个长度为 n 的非负整数数组 height，数组中的每个元素代表垂直线的长度，线的起点在 (i, 0)，终点在 (i, height[i])，i 从 0 到 n-1。

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

注意：你不能倾斜容器。

示例：

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

2. 问题理解

所谓容器，就是选择两个竖直线，容器的底是两条线在 x 轴上的距离（下标差），容器的高度是两条线中较短的那条线的高度（因为水会从短边溢出）。

容器盛水量公式：

\[\text{面积} = \min(height[left], height[right]) \times (right - left) \]

我们要在所有可能的 (left, right) 对中，找到面积的最大值。

3. 思路演进

3.1 暴力法（容易想到但会超时）

枚举所有可能的左右线对，计算面积，取最大值。

def maxArea(height):
    n = len(height)
    max_area = 0
    for i in range(n):
        for j in range(i+1, n):
            h = min(height[i], height[j])
            w = j - i
            max_area = max(max_area, h * w)
    return max_area

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

当 n 很大时（比如 10^5），会超时。

3.2 双指针法（最优解）

核心思想：用两个指针 left 和 right 分别指向数组的左右两端，逐步向中间移动，并记录最大面积。

为什么可以这样做？

1. 初始状态：left = 0, right = n-1，此时底边宽度最大。
2. 移动策略：
   • 计算当前面积。
   • 比较 height[left] 和 height[right]：
     • 如果 height[left] < height[right]，则移动左指针向右（left++）。
     • 否则移动右指针向左（right--）。
3. 终止条件：left >= right。

为什么移动较短的一边是安全的？

• 容器的盛水量由较短的边和底边宽度决定。
• 如果移动较长的一边，那么底边宽度一定会变小，而新的高度不会超过原来的短边高度（因为高度取 min，即使新边更高，高度仍受限于原来的短边或更小），所以面积一定不会变大。
• 如果移动较短的一边，虽然底边宽度变小，但有可能遇到更高的边，从而弥补宽度损失，甚至得到更大面积。

因此，移动短边是不会错过最优解的。

4. 逐步推演示例

数组：[1,8,6,2,5,4,8,3,7]

1. left=0, right=8：

   • 高度 = min(1,7) = 1
   • 宽度 = 8
   • 面积 = 1×8 = 8
   • 移动左指针（因为 1 < 7）

2. left=1, right=8：

   • 高度 = min(8,7) = 7
   • 宽度 = 7
   • 面积 = 7×7 = 49（更新最大值）
   • 移动右指针（因为 7 < 8）

3. left=1, right=7：

   • 高度 = min(8,3) = 3
   • 宽度 = 6
   • 面积 = 3×6 = 18
   • 移动右指针（3 < 8）

4. left=1, right=6：

   • 高度 = min(8,8) = 8
   • 宽度 = 5
   • 面积 = 8×5 = 40
   • 移动任意一边（这里按规则移动右指针，但移动左指针也可以）
   • 假设移动右指针：right=5

5. left=1, right=5：

   • 高度 = min(8,4) = 4
   • 宽度 = 4
   • 面积 = 16
   • 移动右指针

6. 继续这个过程直到指针相遇。

最终最大面积是 49。

5. 代码实现（Python）

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        h = min(height[left], height[right])
        w = right - left
        max_area = max(max_area, h * w)
        
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
            
    return max_area

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

6. 总结

• 本题的关键在于理解双指针移动的合理性：总是移动较短的一边，以期望找到更高的边界来弥补宽度的减少。
• 这种方法确保了在 O(n) 时间内找到最大面积。
• 暴力法虽然直观，但效率低，不适合大数据量。

这样讲解清楚了吗？我们可以继续练习其他题目。