算法 - 盛最多水的容器

Posted on

1. 题目

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

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

说明：你不能倾斜容器。

示例:

1
2
3
4
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
解释: 选择第 2 条线(height=8)和第 9 条线(height=7)，
     宽度 = 9 - 2 = 7，高度取较短板 min(8,7) = 7，面积 = 7 * 7 = 49。

2. 解题思路

2.1 暴力法（不可取）

枚举所有左右边界对 (i, j)，计算 (j - i) * min(height[i], height[j])，时间复杂度 O(n²)，面试中只作为铺垫。

2.2 对撞双指针（最优）

从最宽区间开始，左右指针 l = 0、r = n - 1，每步计算当前面积并更新最大值，然后移动较短的那一边：

  • 容器高度由短板决定。若 height[l] < height[r]，则所有以 l 为左边、右边界在 (l, r) 之间的方案，宽度更小且高度不会超过 height[l]，必然不如当前解——所以可以直接排除 l，令 l++。
  • 反过来移动长板则可能错过更优解，这是正确性的关键。
  • 相等时移动任意一边均可。

每一步排除一个不可能的边界，n-1 步内完成。

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

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function maxArea(height: number[]): number {
    let l = 0;
    let r = height.length - 1;
    let best = 0;

    while (l < r) {
        const h = Math.min(height[l], height[r]);
        best = Math.max(best, h * (r - l));

        // 移动较短的一边，才可能找到更大的面积
        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }

    return best;
}

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49

4. 面试延伸

  • 为什么移动短板？ 反证法：移动长板后宽度必减小，而高度受短板限制不会增大，面积只可能变小；移动短板则高度有可能提升，值得一试。
  • 双指针家族对照：两数之和 II、三数之和、接雨水都用到了对撞指针思想。
  • 常见追问：如果要求输出是哪两条线，只需在更新 best 时记录 l、r 即可。

难度：中等 | LeetCode 11 | 对撞双指针经典题