学习目标

• 能把两条边的高度和间距转化为容器面积，并求出最大值。
• 使用 O(n) 时间的相向双指针算法完成题目。
• 解释为什么每次应该移动当前较短的一侧，而不是枚举所有下标对。

问题描述

给定一个整数数组 height，其中 height[i] 表示坐标 (i, 0) 处一条垂直线的高度。请从中选择两条线，与 x 轴共同组成一个容器，使容器能够容纳的水最多。

容器的两条边必须来自不同下标，且不能倾斜。返回容器可以容纳的最大水量。

下图中，左右两条红色边围成的区域代表一个候选容器；蓝色区域的面积就是它的容量：

下标 l 和 r 形成的容量为：

min(height[l], height[r]) × (r - l)

输入格式

• 第一行输入一个整数 n，表示线的数量。
• 第二行输入 n 个非负整数 height[i]，表示每条线的高度。

输出格式

输出一个整数，表示可以容纳的最大水量。

约束

• 2 ≤ n ≤ 10^5
• 0 ≤ height[i] ≤ 10^4
• 需要使用 O(n) 时间复杂度和 O(1) 额外空间（不计输入数组）。
• 评测输入均符合以上格式与约束；不合法输入不在本题讨论范围内。

示例

示例 1

输入：

9
1 8 6 2 5 4 8 3 7

输出：

49

示例 2：最小规模边界

输入：

2
1 1

输出：

1

思路提示

先令 l = 0、r = n - 1，每次计算当前两条边形成的容量，然后向内收缩区间。

当前容量的高度上限由较短的边决定。无论移动较高的一边，还是保留较短的一边，宽度都会变小；如果短边不变，容量不可能变大。因此，移动较高的一边不会带来更优候选，只有移动短边才有机会找到更高的限制边。两边等高时，移动任意一边都可以，本实现移动右边。

复杂度分析

• 时间复杂度：O(n)，每个指针最多向内移动 n - 1 次。
• 额外空间复杂度：O(1)（不计保存输入数组所需的空间）。

运行与评分

在本 Lab 目录执行：

make doctor
make run
make score

如果没有 Make，也可以在仓库根目录执行：

pnpm lab:run -- labs/chapter-13/exercise/E-13-01-container-with-most-water --target student

参考实现可以用下面的命令验证：

pnpm lab:verify -- labs/chapter-13/exercise/E-13-01-container-with-most-water --no-color

完成清单

• 正确读取 n 和全部高度，并输出一个整数。
• 用双指针避免 O(n²) 的下标对枚举。
• 证明或说明为什么移动短边是安全的贪心选择。
• 覆盖最小规模、全零、两端等高、单调数组和较大高度等情况。

思考与复盘

1. 如果每次移动较高的一边，在哪一步会错过可能的最优解？
2. 两边高度相等时，移动左指针和移动右指针是否会影响正确性？为什么？

题目来源

本题对应 LeetCode 11「盛最多水的容器」：https://leetcode.cn/problems/container-with-most-water/。