当前:LC11 · 盛最多水的容器 · 首次出现于 Day 4 · 路径:顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

LC11 · Container With Most Water · 双指针

盛最多水的容器:谁矮,谁就该挪窝

水面被矮柱卡住。移动高柱,宽变窄、高不变,面积只减;移动矮柱才可能换到更高的边。

左右指针从两端出发。每步用 (j−i)×min(height[i], height[j]) 更新答案,然后只移动较矮的那一侧;两边一样高就移任意一侧。矮边是瓶颈,把它换成更里面的柱才可能抬高水面;高边留下,因为丢掉它不会让当前矮边围出更大的水。时间 O(n),空间 O(1)。

时间 O(n)空间 O(1)结论先行 · 全文约 6 节
导读

这是 LeetCode 11. Container With Most Water。n 条垂直线,第 i 条的两个端点是 (i, 0) 和 (i, height[i])。选两条线当作容器壁,与 x 轴围成矩形,求能盛的最大水量。水不能倾斜,高度取两条线里较短的那条。

主例 height = [1, 8, 6, 2, 5, 4, 8, 3, 7]。最优是下标 1 的 8 和下标 8 的 7:宽度 7,高度 7,面积 49。两端那根 1 和 7 宽度虽是 8,高度被 1 卡住,只有 8。

枚举所有 (i, j) 能做对,n 到 10⁵ 时平方不可用。缺的不是面积公式,而是哪些线对可以成批丢掉。本文从「矮边决定水面」推出谁该往里走,并把手算走到 49。

水量被宽度和矮边同时卡住

两条线 i < j,盛水量是 (j−i) × min(height[i], height[j])。宽是下标差,高是较短的那根——再高的柱也挡不住水从矮的那边溢出去。

目标是最大化这个乘积。暴力枚举全部线对,主例 9 根线 36 对,能得到 49,但没有告诉你下一对该看谁。

从最宽的一对看起。主例 i=0、j=8,高 1 与 7,面积 8。演示第一帧就是这根短板 1。宽已经最大,若还要更大的面积,只能抬高那条矮边。这句观察把「枚举谁」收成「丢掉哪一侧」。

短板公式里的 min 不是实现细节,是决策依据。当前这对的高度上界就是矮柱,任何仍以这根矮柱为边的更窄容器都不可能超过现在。
面积 = 宽度 × 矮柱高度
1
8
6
2
5
4
8
3
7
left=0right=8min(1,7)=1 是短板

每次只移动较矮的那一根

假设 height[i] ≤ height[j],左边是矮边。若移动 j:宽度减 1,高度仍被 height[i] 卡住,面积 ≤ (j−i−1)×height[i] < 当前面积。以这根矮边为左壁的所有更窄容器,都可以丢掉。必须移动 i,去碰一根可能更高的左壁。

右边更矮则移动 j。两边等高,移哪边都一样——下一根柱子才可能打破平局。规则就一句:谁矮谁往里走。

用手走主例。i=0、j=8,面积 8,1<7,i 右移到 1。现在 8 与 7,宽度 7,面积 49,记下最优。8>7,j 左移到 7。现在 8 与 3,面积 18。8>3,j 再左移到 6。现在两根都是 8,宽度 5,面积 40,打不过 49。之后左边 8 一直高于右边,j 一路收到与 i 相遇。全程最优停在 49。演示四帧就是前四次指针:先移左,再连移两次右,停在下标 1 与 6。

比较左右柱高,矮的向内移动
1
8
6
2
5
4
8
3
7
left=0right=8左边 1 ≤ 右边 7 → 移动左边

丢掉的是以当前矮边为壁的更窄容器

每一步淘汰的不是「某一根柱子」,而是「当前矮边与对侧之间所有尚未访问的组合」。这些组合的高度上界仍是这根矮边,宽度还更小,面积不可能超过刚才那对。

最优的那一对 (i*, j*) 不会被跳过。指针从两端往里收,先碰到 i* 和 j* 里更靠外的那一个;另一侧还在更外头。此时靠外的若是矮边,对侧更高,规则会移动矮的,直到另一侧也收到 j* 或 i*;靠外的若是高边,规则移动的是对面,高边留着。两边最终会被同时夹到。主例最优 1 与 8:先丢掉矮边 0,右边 8 一直留到与 1 配对,49 被算到。

两边一样高时移哪一侧都可以,因为以这条高度为矮边的更窄容器同样被当前宽度支配。代码写成 else j--,与 i++ 等价。

七行 Go:双指针

solution.goGo
func maxArea(height []int) int {
i, j, best := 0, len(height)-1, 0
for i < j {
best = max(best, (j-i)*min(height[i], height[j]))
if height[i] < height[j] { i++ } else { j-- }
}
return best
}

1从最宽的一对出发。主例先看下标 0 与 8。

2先算面积再移动。49 出现在 i=1、j=8,必须在 j-- 之前入账。

3严格更矮才动左边;相等走 else,右边内收。不要两边一起动,会跳过最优。

4i==j 时宽度为 0,循环结束。best 里是历史最大。

总结

谁矮谁往里走。主例丢掉短板 1 之后,8 与 7 围出 49,后面再没有更大的。

  • 面积 = 宽度 × 矮边。移动高边,高不变、宽变小,面积只减。
  • 每次丢掉的是「以当前矮边为壁的全部更窄容器」,不是丢掉这根柱子本身。
  • 先记账再移动。主例 49 出现在右指针左移之前。
同族题目
LC42接雨水(更复杂的双指针)LC167两数之和 II(有序数组双指针)LC84柱状图中最大的矩形