暴力到O(n)高效解)
LeetCode第11题“盛水最多的容器”，一道双指针入门必刷题，也是面试里出现频率高得离谱的经典。很多人第一次看到这题，脑子里第一反应就是暴力双重循环，然后交上去发现超时，接着就开始怀疑人生。其实这道题考查的并不是你会不会算面积，而是你能不能从“暴力枚举所有组合”的思维惯性里跳出来，找到那个让搜索空间从O(n^2)降到O(n)的关键结论。这篇文章我会从题目拆解讲起，把双指针为什么正确、代码怎么写、边界怎么处理、变体怎么识别一次说透，最后再聊聊我刷这题时踩过的坑，以及怎么在面试里把这题讲出亮点。
1. 盛水最多的容器：题目到底在问什么
1.1 原题快速还原与痛点定位
题目要求很简单：给你一个非负整数数组height，每个元素代表一条垂直于x轴的线段，起点在(i, 0)，终点在(i, height[i])。要你找出两条线，使得它们与x轴共同构成的容器能容纳最多的水，返回最大面积。
注意，这个“容器”不是封闭的，它只有左右两面墙，没有顶，底部是x轴。所以盛水量由三个因素共同决定：左边墙的高度、右边墙的高度、两墙之间的水平距离。实际盛水高度取决于两堵墙中较矮的那一堵，这就是经典的“短板效应”——一个木桶能装多少水，取决于最短的那块木板。
这道题在LeetCode上的编号是第11题，排在第10题正则表达式匹配和第15题三数之和之间。别看它简单，它和“接雨水”(LeetCode 42)、“最大矩形”(LeetCode 85)都是容器类问题的入门钥匙，而且它考察的双指针思维在后续的题目里反复出现。
我当时第一次刷这题的时候，第一反应就是暴力枚举，把所有(i, j)组合都算一遍，但数组长度最大能有10^5，O(n^2)的复杂度直接劝退。这也是这题的第一个痛点：你第一时间能想到的解法，往往不是题目想要的解法。
1.2 暴力解法先走通，再谈优化
先别急着看双指针，暴力解法再笨，它也是你理解题意的第一步。暴力思路就是两层循环，枚举所有左边界和右边界，算面积取最大值。
public int maxArea(int[] height) { int n = height.length; int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int area = Math.min(height[i], height[j]) * (j - i); ans = Math.max(ans, area); } } return ans; }这个代码没有逻辑错误，但它的时间复杂度是O(n^2)。当n = 10^5时，内层循环要跑大约5 * 10^9次，在大多数在线评测系统中都是稳稳的超时。
面对这种“能算但算不动”的题，你要养成的习惯不是直接去看题解，而是先分析清楚暴力解法到底浪费了什么。在这个题里，它浪费的部分在于：绝大多数的组合根本不需要计算，因为它们的面积不可能是最大值。那怎么判断哪些组合不可能是最大值？这就引申出了双指针的核心逻辑。
2. 双指针思路是怎么从0到1推出来的
2.1 从“短板效应”出发缩小搜索空间
这题的突破口，在于思考“什么情况下面积一定不可能更大”。假设当前你有两个指针left和right，分别指向数组的头和尾，初始宽度最大，面积为：
area = min(height[left], height[right]) * (right - left)此时宽度是全局最大的水平距离。接下来，为了寻找可能更大的面积，你必须往中间移动其中一个指针，宽度必然会变小。既然宽度变小了，想让面积变大，唯一的办法就是让高度变高。而高度由height[left]和height[right]中较小的那个决定。
所以问题就变成了：移动哪一个指针，才可能让“容器高度”变高？
答案很直接：哪个矮就移动哪个。因为如果你移动高的那个，新的容器高度还是受限于矮的那一根，高度不变或者变小，宽度还在变小，面积必然不可能超过当前值。但如果你移动矮的那一根，新的那一侧可能更高，这样容器高度就有机会变大。
我用一个生活中的例子来类比：你在两个不同身高的人之间拉一块布，想让布与地面围成的“影子区域”变大，最值得尝试的动作是换掉那个矮个子，而不是费劲去垫高那个高个子——因为矮个子才是瓶颈。
2.2 双指针为什么不会漏掉最优解：关键证明
很多初学者能理解“移动矮的更好”，但无法理解“这样做一定能找到全局最优解”。这里必须把证明写透。
设当前左右指针为left = i，right = j，且假设height[i] < height[j]。当前面积为S = height[i] * (j - i)。
我们的策略是让i向右移动一步，即抛弃(i, j)这个组合。为什么可以放心抛弃？
对于任意一个以i为左边界的组合(i, k)，其中k满足i < k < j，它的面积为：
S' = min(height[i], height[k]) * (k - i)由于k - i < j - i，宽度比当前小。对于高度：
- 如果
height[k] > height[i]，那么min(height[i], height[k]) = height[i]，高度不变； - 如果
height[k] <= height[i]，那么min(height[i], height[k]) <= height[i]，高度变小或不变。
无论哪种情况，S' <= height[i] * (j - i) = S。也就是说，所有以i为左边界的组合，面积都不可能比当前(i, j)更大。那么左指针i对应的所有状态就都可以整体剪枝，我们直接让i++，完全不会错过全局最优解。
反过来说，如果height[i] > height[j]，那么所有以j为右边界的组合都不可能比当前更大，于是让j--。每次迭代都删除“边界中较矮的一侧”的全部可能性，搜索空间不断收缩，直到左右指针相遇。整个过程只需要O(n)次比较和计算。
这个证明里最关键的一点，就是“宽度减小 + 高度不再增加”这个双重约束。你要理解的是：我们不是比较了两堵墙，而是整批整批地淘汰了不可能成为答案的状态，这才是双指针比暴力高效的本质。
2.3 移动策略的细节：什么时候移动哪个指针
有了证明，移动策略就很清楚了：
- 当
height[left] < height[right]时，left++； - 当
height[left] >= height[right]时，right--。
这里有个容易有争议的细节：当两边相等时，移动哪个？从代码正确性来说，移动哪边都不影响最终结果，因为反正最大值已经记录了。但为了维持循环收敛性，我一般习惯在相等时也移动右指针，比如用if (height[left] < height[right]) left++; else right--;这种写法，else会覆盖等于的情况。
还有一个更激进的优化版本：既然移动矮指针是为了找到更高的墙，如果移动后新墙还是比原矮墙低，那这个位置可以直接跳过。这就是“跳跃式双指针”或者“快速跳过更低墙”的优化方案。思路是：在移动结束后，加一层while判断，如果新位置的高度不比原来的矮墙高，就继续移动。
while (left < right) { int h = Math.min(height[left], height[right]); ans = Math.max(ans, h * (right - left)); if (height[left] < height[right]) { // 跳过所有高度 <= height[left] 的位置 int cur = height[left]; while (left < right && height[left] <= cur) { left++; } } else { int cur = height[right]; while (left < right && height[right] <= cur) { right--; } } }需要注意的是，这种优化在极端数据下（比如[1, 2, 3, 4, 5]）能减少不少比较次数，但它不会改变时间复杂度的大O阶。在面试场景中，先写标准版，再提一手这个优化点，反而是加分项。
3. 核心代码实现与多语言对照
3.1 Java / Python / Go 三种实现直接抄
先给出最标准的双指针解法。我平时刷题主要用Java和Python，Go是最近为了写服务端脚本才补上的，三种语言其实写法几乎一致，核心逻辑就那么几行。
class Solution { public int maxArea(int[] height) { int ans = 0; int left = 0, right = height.length - 1; while (left < right) { int area = Math.min(height[left], height[right]) * (right - left); ans = Math.max(ans, area); if (height[left] < height[right]) { left++; } else { right--; } } return ans; } }Python版更简洁，配合List[int]类型注解看起来非常舒服：
class Solution: def maxArea(self, height: List[int]) -> int: left, right = 0, len(height) - 1 ans = 0 while left < right: h = min(height[left], height[right]) area = h * (right - left) ans = max(ans, area) if height[left] < height[right]: left += 1 else: right -= 1 return ansGo版需要注意的是没有内置的min函数（Go 1.21之前），要自己写一个或者用标准库。我在Go里面一般选择不引入额外依赖，自己写一行判断：
func maxArea(height []int) int { left, right := 0, len(height)-1 ans := 0 for left < right { h := height[left] if height[right] < h { h = height[right] } area := h * (right - left) if area > ans { ans = area } if height[left] < height[right] { left++ } else { right-- } } return ans }3.2 复杂度分析与边界情况核对
时间复杂度O(n)，因为left和right总共移动n次，每次只做常数时间的操作。空间复杂度O(1)，只用了几个变量，没有额外数组。
边界情况是这种题最容易翻车的地方：
- 数组长度为2：
[1, 2]，左右指针相邻，只算一次面积1 * 1 = 1，返回1。正确。 - 所有高度相等：
[3, 3, 3]，面积最大是3 * 2 = 6，双指针对称收紧，结果正确。 - 高度递增：
[1, 2, 3, 4, 5]，最左和最右组合1 * 4 = 4，中间会有更大的组合吗？2 * 3 = 6，所以答案是6。 - 数组长度为1或0：题目约束一般
n >= 2，但为了健壮性，可以加一个if (height.length < 2) return 0;的防御性判断。
我在刷题时会额外注意整数溢出问题。这道题里高度最大值不会超过10^4，宽度也不会特别离谱，int足够。但如果数组元素范围是10^9级别（比如某些变体题），Long或者大数类型就要考虑进来了。
3.3 代码里的三个易错点，我全踩过
第一个易错点是在更新面积前就移动了指针。比如想当然写成left++再算面积，你会发现宽度少了1，结果完全不对。正确顺序必须是：先根据当前left和right计算面积并更新答案，再移动指针。
第二个易错点是循环终止条件写成left <= right。当left == right时，左右指针指向同一根柱子，容器宽度为0，虽然面积也是0不影响最终答案，但逻辑上已经没有意义了。建议统一用left < right，语义更清楚。
第三个易错点在移动指针时的条件判断写反，写成if (height[left] > height[right]) left++。这个错误尤其隐蔽，因为当数组是递增序列时，这种写法有时候也会碰巧算出正确答案，但整体逻辑是错的，遇到随机数组就会挂。移动矮侧是铁律，别凭感觉改。
4. 这类题的识别套路：怎么知道该用双指针
4.1 双指针题型的典型特征画像
很多人刷题靠“背模板”，但真正高效的方式是建立“条件反射”。哪些题应该考虑双指针？我总结出几个信号：
第一，题目涉及两个元素之间的某种关系，比如总和、差值、面积、距离、最大水容量。
第二，暴力解是O(n^2)的双重循环，且数据范围在10^5以上。
第三，数组本身无序，或者说不依赖排序就能通过“移动端点”的方式来缩小搜索空间。
第四，计算出的某个值只由两个端点决定，中间元素不影响结果。
这题完美符合以上所有特征。一旦识别出来，就能快速判断：不是哈希表方案、不是排序方案、不是动态规划方案，而是相向双指针。
4.2 相向双指针 vs 同向双指针：怎么区分
双指针分两大流派：相向双指针和同向双指针。
相向双指针就是这题用的，左右两端向内收缩，常用于数组有序或半有序场景下的两数之和、回文判断、盛水容器等。它的核心是“每次排除掉一边的无效区间”，所以必须能证明被排除的那一侧不可能产生更优解。
同向双指针也叫滑动窗口，两个指针都从左往右走，常用于满足某种条件的连续子数组问题，比如“长度最小的子数组”(LeetCode 209)、“无重复字符的最长子串”(LeetCode 3)。它的核心是“维护一个窗口，通过右指针扩大、左指针收缩来寻找可行解”。
区分方法很简单：两端收缩，排除的是“区间外不可能”，是相向；一端扩张一端收缩，维护的是“当前窗口合法性”，是同向。这题是前者，因为不存在“窗口”的概念，讨论的永远是最外侧两条线。
4.3 与相邻模板题的对比：接雨水与最大矩形
盛水最多的容器(11)、接雨水(42)、最大矩形(85)经常被放在一起比较。它们的共同点是都涉及“柱子”和“面积”，但解法思路完全不同。
接雨水是计算所有凹陷处能存的雨水总量，用的是单调栈或者左右最高柱子的“前缀最大/后缀最大”思想。它关注的是每个位置上方能存多少水，依赖两侧最高柱子的较小值减去当前高度。
最大矩形（柱状图中最大的矩形）则是在直方图里找面积最大的矩形，核心是单调栈，找每个柱子左右两侧第一个比它矮的位置，以当前柱高为矩形高。
盛水容器则只关注两堵墙之间的最大面积，双指针直接在端点收缩即可，完全不需要单调栈。我在复习的时候，会把这三题放到一起看，对比它们的“面积计算方式”和“数组遍历方式”，这样印象会深很多。
有读者问过我：为什么接雨水不能用盛水容器的双指针解法？因为接雨水关心的是所有位置的水量累积，而盛水容器只关心一对墙的极值。目标函数不同，对应算法自然不同，别看到“柱子+面积”就往一个模板里套。
5. 常见问题与排查技巧实录
5.1 新手最容易犯的4个错误，附排除方法
这里直接上我刷题和看群友提问时汇总的常见问题速查表。
| 问题现象 | 根因 | 排查/修正方法 |
|---|---|---|
| 输出结果比预期小 | 先移动指针后计算面积，宽度少了1 | 调整代码顺序，务必先算面积再动指针 |
| 输出结果比预期大 | 把height[left]和height[right]中大的那个当成了容器高度 | 检查是否用了Math.max而不是Math.min |
| 部分用例超时 | 误用了O(n^2)暴力解法 | 换双指针，确认循环里每次只移动一个指针 |
| 数组长度为2时答案错误 | 边界初始化或循环终止条件写错 | 单步调试，确认left=0, right=n-1, while(left<right) |
这些错误里，“把Math.max写成Math.min”是尤其常见的，因为很多人看到“最多”两个字，就不自觉把面积里的“高度”也取大了。请记住：面积 = 最小高度 × 宽度，这个最小高度是不能用“最大化目标”替代的。
5.2 从周赛430看命题趋势：双指针还能怎么考
最近LeetCode周赛430里有几道题也涉及了双指针的变形，比如需要结合哈希表记录出现的次数，或者结合前缀和做预处理。这说明双指针很少单独出现，它更像是一个“基础骨架”，常常要跟其他数据结构组合使用。
举例来说，如果题目改成“求最大面积，但要求两条墙的下标差不小于k”，你仍然可以用双指针，只是在更新答案时加一个if (right - left >= k)的判断。再比如“求水的体积但墙体本身有厚度”，那就需要给宽度部分减去墙体的实际厚度，核心逻辑完全不变。
我在备战周赛时，习惯把这类题归纳为“双指针 + 条件剪枝”。建议读者在刷题时，不满足于AC一道题，多做一步变形思考：如果数组有序能用吗？如果要求返回下标呢？如果允许修改数组呢？这些都会显著提升你的应对能力。
5.3 面试讲解这题的口径与实战心得
如果在面试里遇到这题，代码写出来只是第一关，你需要把思路讲清楚。我建议按这四步来组织语言：
第一步，说明暴力解法的局限。可以说：“最直观的做法是枚举所有左右边界组合，复杂度是O(n^2)，在n较大的情况下不可行。”
第二步，指出现象。说：“我们发现，当左右指针指向两根柱子时，容器的高度取决于较短的那根。如果将较长端向内移动，宽度减小且高度不可能增加，因此面积必然减小。所以移动较矮端才有意义。”
第三步，给出证明。“每次移动较矮端，相当于排除了所有以它为边界的候选组合，因为其中任一组合的面积都被当前面积上界限制。”
第四步，给出复杂度。“左右指针最多各移动n次，总体O(n)时间，O(1)空间。”
这套讲法既体现了你的算法功底，也展示了数学证明能力，比上来就甩代码要加分得多。我自己面试候选人的时候，只要对方能讲到第三步的证明，这道题基本就给过了。
最后再分享一个小技巧：我在LeetCode上刷到这道题时，学到的不仅是双指针，更重要的是“如何证明贪心选择的正确性”。此后我遇到类似问题，都会刻意追问自己一句——这一步贪心会漏掉最优解吗？这个习惯帮我解决了很多难题，也让我的刷题效率提升了一大截。
