盛最多水的容器

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：数组、双指针、贪心算法

给定一个长度为 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

2. 解题思路拆解

方法：双指针（对撞指针）

容器的面积由两个因素决定：

底边的宽度：两条线之间的距离。
两边的高度：两条线中较短的那一条（木桶效应）。

公式：$Area = \min(height[left], height[right]) \times (right - left)$

贪心策略：我们希望面积最大。

初始时，选择最宽的容器，即左指针 left 指向数组开头，右指针 right 指向数组末尾。
此时宽度最大，我们需要思考如何移动指针才能让面积变大？
- 如果我们移动较长的那根柱子，宽度变小了，而高度受限于较短的那根柱子（瓶颈），所以新的高度肯定不会超过原来较短的那根。因此，面积一定变小。
- 如果我们移动较短的那根柱子，宽度变小了，但新的柱子有可能比原来较短的这根更高，从而使得整体高度变高，面积有可能变大。

结论：每次都移动较短的那根柱子指向的指针，并更新最大面积，直到两个指针相遇。

3. 代码实现

javascript

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let left = 0;
    let right = height.length - 1;
    let maxVal = 0;

    while (left < right) {
        // 1. 计算当前面积
        const w = right - left;
        const h = Math.min(height[left], height[right]);
        const currentArea = w * h;

        // 2. 更新最大面积
        maxVal = Math.max(maxVal, currentArea);

        // 3. 移动较短的柱子
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxVal;
};

代码执行演示

输入 height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

初始：L=0 (1), R=8 (7)。宽=8, 高=1。Area = 8。
- 1 < 7，移动左指针。L -> 1。
Step 2：L=1 (8), R=8 (7)。宽=7, 高=7。Area = 49。
- 8 > 7，移动右指针。R -> 7。
Step 3：L=1 (8), R=7 (3)。宽=6, 高=3。Area = 18。
- 8 > 3，移动右指针。R -> 6。
Step 4：L=1 (8), R=6 (8)。宽=5, 高=8。Area = 40。
- 8 == 8，移动任意一个（这里假设移右）。R -> 5。
...后续步骤继续收缩，直到 L 和 R 相遇。
最终最大值为 49。

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。双指针总共遍历数组一次。
空间复杂度	$O(1)$。只使用了常数个变量。

盛最多水的容器 ​

1. 题目呈现 ​

2. 解题思路拆解 ​

方法：双指针（对撞指针） ​

3. 代码实现 ​

代码执行演示 ​