11. 盛最多水的容器（中等）

Blind 75 › 11. 盛最多水的容器（中等）（第 3 章）

题目

给定一个整数数组 height，下标 i 处有一条竖直的线，两端点分别是 (i, 0) 与 (i, height[i])。任选两条线，它们与 x 轴一起围成一个开口容器。

这个容器能装多少水，由两个量决定：两条线的水平距离（宽度），以及两条线中较矮的那一条（高度）。即 水量 = 宽度 × min(两条线高度)。求所有选法中能容纳的最大水量，容器不能倾斜。

自造示例：height = [3, 1, 2, 5, 4]。选下标 (0, 4)：宽度 4，高度 min(3, 4) = 3，水量 12；其他组合如 (0, 3) 水量 9、(3, 4) 水量 4，所以最大水量为 12。

约束：2 ≤ n ≤ 10⁵；0 ≤ height[i] ≤ 10⁴；容器不能倾斜。

一句话：容器只由“宽度”和“较矮的那条线”决定；左右指针从两端相向收缩，每次放弃较矮的一侧。

先想最直白的做法：枚举所有线对 (i, j)，逐个计算 (j - i) * min(height[i], height[j])，并保留最大值。这需要 O(n²) 次计算；当 n = 10⁵ 时约 10¹⁰ 次，明显超时。

关键观察：设当前左右端点为 l 与 r，且 height[l] ≤ height[r]。任何以 l 为左端点的其他容器 (l, k)，宽度都比 r - l 更小，而高度又不可能超过短板 height[l]；所以它们的水量一定不会超过当前 (l, r)。

也就是说，此时左端点 l 已经不可能参与更优解，可以安全向右移动。对称地，如果右端更矮，就移动右端。于是得到简单规则：谁矮移动谁；两端相等时移动任意一端都不影响正确性。两端相遇时，所有可能成为最优的候选都被检查过了。

用左右双指针从数组两端向中间收束，过程中维护最大值：

以自造示例 [3, 1, 2, 5, 4] 走一遍：

轮次	left	right	左高	右高	宽度	面积	当前最优	动作
1	0	4	3	4	4	12	12	左矮，`left++`
2	1	4	1	4	3	3	12	左矮，`left++`
3	2	4	2	4	2	4	12	左矮，`left++`
4	3	4	5	4	1	4	12	右矮，`right--`

随后 left == right，停止，返回 12。

下图把上面 4 个步骤串成流程，并逐步演示：

C++ 片段需补全 main() 函数才能运行在实训台打开 →

class Solution {
public:
 int maxArea(vec
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。