#11. 盛最多水的容器

LeetCode 原题链接

#题目描述

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

从中选择两条线，使它们与 x 轴共同构成一个容器，返回容器能够盛水的最大值。容器不能倾斜。

示例：

输入：height = [1,8,6,2,5,4,8,3,7]
输出：49
解释：选择下标 1 和 8，高度分别为 8 和 7。
     面积 = min(8, 7) * (8 - 1) = 49。

#1. 题型判断

选择下标 left 和 right 作为容器两侧时，容量为：

area = min(height[left], height[right]) * (right - left)

暴力解法需要枚举所有下标对，共有 O(n²) 个候选。

面积由两个因素决定：

• 宽度：right - left。
• 有效高度：两侧高度的较小值。

如果从数组两端开始，当前宽度已经是该区间能取得的最大宽度。接下来无论移动哪一侧，宽度都会减小；若想得到更大的面积，就只能设法提高有效高度。因此，每轮应移动较矮的一侧，寻找更高的边界。

这是一道典型的相向双指针 + 贪心排除问题。

#2. 指针含义

使用闭区间 [left, right]：

• left：当前容器的左边界，从数组开头向右移动。
• right：当前容器的右边界，从数组末尾向左移动。
• ans：到目前为止见过的最大面积。

初始时：

let left = 0;
let right = height.length - 1;

这样第一次计算使用了最大宽度。随后两个指针只向中间移动，直到相遇。

#3. 为什么移动较矮的一侧

假设当前有：

height[left] <= height[right]

当前面积为：

height[left] * (right - left)

此时固定 left，把 right 移到区间内任意位置 k：

• 新宽度 k - left 一定小于 right - left。
• 新的有效高度 min(height[left], height[k]) 不会超过 height[left]。

因此，所有以 left 为左边界、右端点位于当前区间内的容器，都不可能比当前容器面积更大。left 已经可以安全排除，应执行 left++。

同理，当 height[left] > height[right] 时，应排除 right，执行 right--。

这也是算法的核心不变量：每次移动指针时，被排除的短板不可能再参与构成更优解。

当两侧等高时，移动任意一侧都正确。代码中统一移动右指针即可。

#4. 答案更新时机

每轮先用当前的两个边界计算面积，再移动较矮的一侧：

const area = Math.min(height[left], height[right]) * (right - left);
ans = Math.max(ans, area);

不能先移动再计算，否则会漏掉当前这对边界。

#5. 示例推演

以 height = [1,8,6,2,5,4,8,3,7] 为例：

指针相遇后结束，最终答案是 49。

#6. 边界条件与易错点

边界条件：

• 题目保证至少有两条线，因此可以直接初始化首尾指针。
• 两侧高度相等时移动任意一侧均可，不会漏掉更优解。
• 高度为 0 时不需要特殊处理，当前面积自然为 0。
• 单调递增、单调递减以及所有高度相同的数组都适用同一套逻辑。

易错点：

• 面积的高度是 Math.min(height[left], height[right])，不是较大值。
• 宽度是下标之差 right - left，不是元素个数 right - left + 1。
• 必须移动较矮的一侧。移动较高的一侧只会让宽度变小，而有效高度仍受较矮侧限制。
• 循环条件是 left < right；两指针相遇时无法形成容器。
• 不要只写“移动短板”，面试时应说明被排除端点为什么不可能组成更大的面积。

#7. 代码实现

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

  while (left < right) {
    const width = right - left;
    const currentHeight = Math.min(height[left], height[right]);
    ans = Math.max(ans, width * currentHeight);

    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return ans;
};

#8. 复杂度分析

• 时间复杂度：O(n)。left 和 right 最多各移动 n - 1 次，每轮操作都是 O(1)。
• 空间复杂度：O(1)。只使用了常数个变量。

相比之下，暴力枚举所有两条线的组合需要 O(n²) 时间。

#9. 面试追问

#为什么不能移动较高的一侧？

假设左侧较矮。移动右侧后宽度变小，而有效高度仍然不可能超过左侧高度，所以面积一定不会超过当前面积。只有移动左侧，才有机会找到更高的短板来弥补宽度损失。

#能否一次跳过所有不高于当前短板的柱子？

可以。例如左侧较矮时，可以连续跳过所有 height[next] <= height[left] 的位置，因为这些位置宽度更小、有效高度也没有提高，不可能得到更大面积。这是一种常数级优化，但每个下标本来就只处理一次，因此整体时间复杂度仍是 O(n)。

#双指针为什么不会漏掉最优解？

每轮都计算当前端点对的面积，然后只删除已经证明不可能与区间内其他端点构成更优解的短板。由于每次排除都有严格依据，最优解要么已经被计算过，要么它的两个端点仍保留在后续区间中。

#10. 可迁移总结

本题的关键不是记住“左右指针向中间移动”，而是理解排除逻辑：

1. 从最大宽度开始计算。
2. 宽度缩小不可避免，要提升面积只能期待有效高度增大。
3. 保留较高边界，移动限制当前面积的较矮边界。
4. 用证明过的排除规则，把 O(n²) 个下标对压缩为 O(n) 次检查。

遇到“从两端选择元素，结果同时受距离和较弱一侧限制”的问题时，可以优先考虑相向双指针，并判断是否存在类似的安全排除规则。