11. 盛最多水的容器

题目

力扣题目

给定一个长度为 n 的整数数组 height。第 i 条垂线的两个端点是 (i, 0) 和 (i, height[i])。找出两条线，使它们与 x 轴共同构成的容器可以容纳最多的水，返回最大水量。容器不能倾斜。

示例 1：

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

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

考察内容

• 相向双指针
• 容器面积公式
• 移动较短边的贪心选择
• 排除不可能更优的状态
• 从 $O(n^2)$ 枚举优化到 $O(n)$

解题思路

暴力枚举

枚举任意两条线 i 和 j，容器宽度为 j - i，有效高度由较短的线决定：

共有 $O(n^2)$ 对线，因此暴力法无法满足较大的数据规模。

相向双指针

初始时让 left 和 right 分别指向数组两端，此时容器宽度最大。每轮计算当前面积，然后移动高度较小的一侧：

• 若 height[left] < height[right]，移动 left；
• 否则移动 right。

为什么只能移动短边？假设左边更短，即 height[left] <= height[right]。如果保留左边、只把右边向内移动：

• 新容器宽度一定变小；
• 新容器高度最多仍为 height[left]；
• 因此面积不可能超过当前面积。

所以所有保留当前短边的更窄容器都可以直接排除。只有移动短边，才有机会遇到更高的边，用高度增长弥补宽度损失。

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

1. left = 0、right = 8：面积为 8 × min(1,7) = 8，移动较短的左边；
2. left = 1、right = 8：面积为 7 × min(8,7) = 49，得到最大值；
3. 指针继续向中间移动，检查剩余可能性。

两个指针总共最多移动 n - 1 次：

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

代码演示

int maxArea(const std::vector<int>& height) {
    int left = 0;
    int right = static_cast<int>(height.size()) - 1;
    int result = 0;

    while (left < right) {
        int width = right - left;
        int h = std::min(height[left], height[right]);
        result = std::max(result, width * h);

        // 移动短边，才有可能获得更大的有效高度
        if (height[left] < height[right]) {
            ++left;
        } else {
            --right;
        }
    }

    return result;
}

易错点

• 面积使用两边高度之和或较大值：水面高度取决于短板，应使用 min(height[left], height[right])。
• 宽度多算一位：坐标间距是 right - left，不是数组元素数量 right - left + 1。
• 移动较高的一侧：宽度变小而短板不变，不可能得到更大面积；应移动较短的一侧。
• 只比较高度，不计算每轮面积：当前指针对也可能是最优解，移动前必须先更新答案。
• 循环条件写成 left <= right：两个指针相遇时宽度为 0，无需处理，使用 left < right。
• 先排序数组：下标距离就是容器宽度，排序会破坏原始位置关系。

总结

面积同时受宽度和短边高度限制。双指针从最大宽度开始，每轮移动短边，安全地排除一批不可能更优的组合，将枚举所有线对的 $O(n^2)$ 解法优化为 $O(n)$。

相关题目

• 42. 接雨水
• 167. 两数之和 II - 输入有序数组
• 977. 有序数组的平方
• 881. 救生艇