1. 为什么第一反应是枚举而枚举又行不通1.1 暴力解法的直觉从哪来第一次见到“盛最多水的容器”这道题几乎所有刷过 LeetCode 的人第一反应都是同一个把所有柱子两两组合算一遍面积取最大值不就行了两根柱子配一个容器暴力枚举所有(i, j)组合这个思路完全符合正常人的直觉没有任何弯弯绕绕。把题目翻译成人话给定一个非负整数数组height里面每个数字代表一根竖立在 x 轴上的柱子的高度。现在选两根柱子连同 x 轴一起围成一个“容器”问这个容器最多能装多少水。装水的多少取决于两个东西容器的高度由两根柱子中较矮的那根决定这就是木桶效应容器的宽度则是两根柱子在数组中的距离。于是面积公式非常直白S min(height[i], height[j]) * (j - i)暴力解法的代码也就三五行def max_area_bruteforce(height): n len(height) ans 0 for i in range(n): for j in range(i 1, n): ans max(ans, min(height[i], height[j]) * (j - i)) return ans逻辑没有毛病样例也能一眼跑对。但问题在于这个解法的复杂度是 O(n^2)而题目给出的数据范围通常到 10^5 级别。10^5 根柱子意味着大约 5 × 10^9 个组合要算这个量级在力扣的测评机上基本就是“提交即超时”的命运。1.2 暴力枚举的价值不是 AC而是定义搜索空间很多人刷题有个坏习惯看到暴力解会超时就直接跳过赶紧去背“最优解”。但暴力解其实有一个无可替代的价值——它完整地定义了这个问题的解空间。所有可能的容器组合就是一个巨大的上三角矩阵坐标(i, j)代表“以第 i 根柱子和第 j 根柱子为边界”的候选答案。暴力解做的事情就是把这个矩阵里的每一个格子都遍历一遍而任何更聪明的算法本质上都是在想办法少看一些格子并且还得保证“被跳过的格子里没有全局最优解”。“盛最多水的容器”真正的核心不是怎么枚举而是凭什么敢少枚举。这也是为什么这道题在 LeetCode 热门 100 题里的位置非常特殊它代码短但它逼着你思考一个硬核问题——如何证明一部份候选解可以安全丢弃。想明白这个问题比 AC 本身值钱得多。2. 双指针解法的核心短边才是真正的天花板2.1 从最宽状态出发为什么不能乱动既然暴力枚举行不通那就得找规律。先别急着想怎么优化我们把视角拉回面积公式$$S \min(h[L], h[R]) \times (R - L)$$一开始我们把两个指针放在数组的两端也就是L 0、R n - 1。这个状态的宽度是全局最大的。虽然两边高度不一定是最大的但宽度已经拉满了。下一步必然要让某个指针向内收缩因为两根柱子一旦选中容器范围就固定了不存在“向外扩”的可能性。问题变成向内收缩的时候动左边还是动右边这里就是整道题的灵魂所在。我们假设当前状态中h[L] h[R]也就是左边矮、右边高。现在有两种移动方式移动高的那一侧R 向左移动矮的那一侧L 向右。直觉告诉我们应该去动“看起来不重要”的那根。但很多人第一次做这题会下意识觉得“矮的那根是瓶颈我得换掉它”这个想法是对的也有人会想“高的那根更有潜力把它往里收一点说不定能遇到更均衡的组合”这个想法就是掉坑里了。2.2 移动长边为什么等于白走一步如果移动 R长边一侧由于 L 没变容器的高度依然被h[L]压着。而宽度(R - L)变小了。两个因子里面高度不可能超过原来的h[L]宽度又一定变小那面积怎么可能超过当前值用数学式子看更清楚。移动 R 到某个位置R且L R R$$S \min(h[L], h[R]) \times (R - L) \le h[L] \times (R - L) h[L] \times (R - L) S$$结论非常干脆只要移动长边新状态的面积严格小于当前面积。换句话说这一步绝对不可能刷新答案走了等于白走。2.3 移动短边为什么有机会翻盘反过来移动 L短边一侧就不一样了。虽然宽度同样变小了但新位置的柱子高度可能很高容器的高度不再被原来的短边锁死。一旦新的h[L]足够大面积就可能压过当前值。注意这里说的是“有机会”不是“一定”。移动短边也可能得到更小的面积但至少没有把可能性彻底堵死。所以双指针的移动策略就一句话每次都把较矮的那一侧往中间移动。如果两边高度相等动哪一边都可以原因后面会专门讲。这个策略的底层逻辑用一句话可以概括短边是当前容器真正的天花板任何以它为边的容器都不可能超过它现在贡献的上限所以该换的是它而不是那个还能继续扛事的长边。3. 严谨性检查凭什么说双指针不会漏掉最优解3.1 用“剪枝”的视角看指针移动背出双指针写法很简单但面试官真正想听的是“为什么这样移动不会错过最优解”。这一节我们把这个证明补上。假设当前指针位置是L和R并且h[L] h[R]。当前面积$$S h[L] \times (R - L)$$因为min(h[L], h[R]) h[L]所以面积就是左矮柱的高度乘以宽度。现在考虑任意一个以L为左边界、右边柱子k落在(L, R)区间内部的候选容器。不管k在哪新容器的高度都被min(h[L], h[k])限制住而这个值最多也只有h[L]同时宽度(k - L)严格小于(R - L)。于是$$S_k \min(h[L], h[k]) \times (k - L) \le h[L] \times (R - L) S$$也就是说所有以当前短边L为左边界的候选容器面积都不会超过当前这一轮算出来的面积。而当前面积在这一轮循环里已经更新进了ans。所以整行候选全部“废掉”可以放心地把L向右移一位不用担心丢掉最优解。h[R] h[L]的情况完全对称所有以R为右边界的候选容器面积都不会超过当前面积R向左移是安全的。3.2 相等高度时为什么移动哪边都对两边高度相等也就是h[L] h[R]时上面的两种论证同时成立。既可以说“所有以 L 为左边界的候选都不超过当前面积”也可以说“所有以 R 为右边界的候选都不超过当前面积”。因此代码里无论写left还是right--都能得到正确答案。这也是为什么网上各种题解在相等分支的处理上写得五花八门——有的用else left有的用else right--还有的用if...else覆盖相等情况结果都对。不是某个写法有隐藏 bug而是两边都安全。3.3 反证法一步到位如果觉得上面的“整行剪枝”说法不够有冲击力可以换一个反证法的表述。假设全局最优解存在于某个位置(L*, R*)并且我们的算法漏掉了它。那一定存在某次循环恰好L走到L*的位置、R还在R*的右边但此时我们把L*直接跳过了。这种情况只会发生在h[L*] h[R]或者相等时按代码选择了移动 L的前提下。而根据 3.1 的推导所有以L*为左边界、右边界在(L*, R)之间的候选容器面积都不会超过当前面积更不会超过当前维护的全局最大值ans。这就和“(L*, R*)是全局最优解”矛盾。漏不掉所以算法正确。这套证明的思路很值得记住。以后遇到别的双指针问题也可以照着这个模板写一遍先说明“某一侧的候选全都不优于当前值”然后理直气壮地移动指针。4. 完整推演标准用例从开头走到结尾4.1 一步步看指针怎么动理论说完了拿力扣自带的经典用例来跑一遍height [1, 8, 6, 2, 5, 4, 8, 3, 7]下标从 0 开始数组长度 9。按照“移动较矮一侧、相等时移动右侧”的策略完整过程如下表轮次LRh[L]h[R]宽度面积当前最大值谁在移动10817888L1 72188774949R8 73178361849R8 34168854049R相等5158441649R8 46148531549R8 5713822449R8 2812861649R8 6第 8 轮结束后 L 和 R 相遇循环终止最终答案是 49。4.2 这个推演暴露出的三个关键事实第一个事实最优解 49 在第二轮就已经出现了后面所有轮次的面积都小于它。这说明双指针不是“一步一步逼近最优解”而是一路在排除“不可能更优”的候选。最大值在哪一轮出现并不重要重要的是这一轮一定会被遍历到。第二个事实这个用例里 8 号柱下标 1异常地高导致它一整路都在当“长边”右边的指针一路收缩到它旁边。这种“一边倒”的情况很常见恰恰说明剪枝的效率——如果某根柱子一直是当前最矮边外侧的高柱另一侧会快速扫过中间大量无效区域。第三个事实如果相等时改成移动 L结果依然是 49。不信你可以自己按表格改一遍在第 4 轮选择移动 L后续路径会切换到以 6 号柱下标 6为右边界的剪枝过程但最终最大值不变。这就是上一节证明的“相等两边都安全”在真实数据上的验证。5. 代码落地Java、Python、C 实现与细节5.1 三种常用语言的版本Java 版本国内面试写的最多class Solution { public int maxArea(int[] height) { int left 0, right height.length - 1; int ans 0; 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 版本刷题时用来快速验证思路def max_area(height): left, right 0, len(height) - 1 ans 0 while left right: area min(height[left], height[right]) * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ansC 版本竞赛选手的最爱class Solution { public: int maxArea(vectorint height) { int left 0, right height.size() - 1; int ans 0; while (left right) { int area min(height[left], height[right]) * (right - left); ans max(ans, area); if (height[left] height[right]) { left; } else { --right; } } return ans; } };先算面积、再更新答案、最后移动指针这个顺序不要乱。如果把指针移动写在面积计算前面第一轮就会漏掉L 0, R n - 1这个初始状态答案会错。5.2 复杂度为什么是 O(n) 而不是 O(n 的一半) 之类时间上两个指针从两端出发相向而行每轮只移动一个指针每个元素最多被指针扫过一次所以是 O(n)。空间上只用了两个整型变量O(1) 额外空间。这个复杂度基本就是本题的最优了。虽然从“读数组”的角度看你至少得把所有柱子高度看一遍才知道最高峰在哪所以 O(n) 的下界很自然。双指针真正牛的地方在于它没有用排序、没有用哈希表、没有开额外数组就在原数组上扫地一样走了一遍把 O(n^2) 的搜索空间压缩成了 O(n)。6. 容易翻车的几个点以及我实测过的微优化6.1 五个高频错误现场第一个错误是移动方向写反。有人会把比较条件和指针移动写岔if height[left] height[right]: right - 1 else: left 1这就等于每次都在移动长边面积只会越算越小最优解直接被跳过。用前面的用例跑一遍可以得到 40 甚至别的错误答案。这个错误背后的心理动因很有意思有人误以为是“矮边限制了高度我要把矮边保留住”但实际上保留矮边等于保留了天花板真正该换的就是矮边。第二个错误是循环条件写成left right。左右指针相遇时宽度为 0算出来的面积也是 0不影响最终结果但白白多算一轮。更重要的是逻辑上不够干净写完自己看着也别扭。这个题while (left right)是正解。第三个错误是忘记取最小值。有人直接把height[left] * height[right] * (right - left)当面积这是拿两根柱子拼矩形不是装水。容器能装多少水取决于短板不取决于长板。第四个错误是更新答案的时机不对。先移动指针再算面积会漏掉第一轮的初始最大宽度状态先移动指针再更新ans还可能把中间某些有效状态漏掉。正确顺序就是上面代码里那样算面积 - 更新答案 - 移动指针。第五个错误是忽视数组太短的健壮性。题目保证了height.length 2但如果你把这段代码抽出来做工具函数最好加一行判空和长度判断if height is None or len(height) 2: return 06.2 要不要做“跳过更矮柱子”的优化网上有些题解会在移动指针之后加一个 while 循环跳过所有“不高于当前短边”的柱子写成这样def max_area_optimized(height): left, right 0, len(height) - 1 ans 0 while left right: h_left, h_right height[left], height[right] ans max(ans, min(h_left, h_right) * (right - left)) if h_left h_right: left 1 while left right and height[left] h_left: left 1 else: right - 1 while left right and height[right] h_right: right - 1 return ans这个优化的逻辑是既然刚刚已经确认“以当前短边为边界的候选都不会超过当前面积”那移动之后如果新位置的高度还不如原来的短边它更加不可能翻盘可以继续跳。推导是成立的但这个优化在力扣的测试数据上收益非常有限。原因很简单基础版本来就是 O(n)100000 个数据点跑一遍只要几十毫秒你再怎么跳也不可能跳出量级级别的差距。我的实测建议是日常刷题和面试写基础版就够了代码可读性最好不容易写错。跳跃版可以作为思维练习自己推导一遍理解它为什么安全但没必要背下来。真到了面试现场你花 30 秒写基础版再用 30 秒把剪枝证明讲清楚比甩一个加了三个 while 的“优化版”有用得多。7. 从盛水容器到对撞指针一类题目的通用思考框架7.1 把候选解想象成矩阵双指针就是在消行消列学到这如果只把“盛最多水的容器”当成一道题来记那有点亏。它真正的价值是提供了一个可以迁移到很多问题上的思考框架。前面提到所有候选解可以看成一个上三角矩阵横坐标是左指针纵坐标是右指针。双指针每移动一次其实是在消掉一整行或者一整列。为什么复杂度是 O(n)因为从右上角走到左下角这个过程最多消 n 行加 n 列总共 2n 步封顶。这个“矩阵消行消列”的视角我后来在很多对撞指针题里都用得上。拿到新题先画出候选矩阵然后问自己当前这一步我有没有一个铁的理由能说明某一行或某一列不可能包含最优解如果能双指针就成立了。7.2 同类题怎么套这个框架LeetCode 上有一串题本质都是对撞指针第 167 题“两数之和 II - 输入有序数组”当前和大于 target 时右指针左移是安全的因为左指针已经是最小值和它配更小的数只会更小第 15 题“三数之和”固定一个数后剩余区间用对撞指针依据是排序后的单调性第 16 题“最接近的三数之和”同样是对撞加绝对值比较第 42 题“接雨水”表面上是另一套逻辑但核心直觉“哪边矮就从哪边开始算”与本题如出一辙第 611 题“有效三角形的个数”固定最长边之后用对撞指针统计排除依据是两边之和大于第三边。这些题都有一个共同点都可以先从暴力枚举出发然后找到一个严格的“指针移动依据”把搜索空间砍半再砍半。而“盛最多水的容器”是所有这类题里移动依据最容易讲清楚、证明最简短的一道。所以刷 LeetCode 热门 100 题的时候我强烈建议把这一题放在双指针专题的第一位先把证明啃下来后面一串题都会顺很多。我个人刷这题的经验是AC 只是及格线真正的收获在于能合上答案用五分钟时间把“为什么移动短边不会漏解”完整推一遍。你能在白板上把这个证明写出来这道题才算真正属于你了。后续做接雨水、三数之和的时候我经常还会绕回这个证明来找手感——短边是天花板该换的是一个容器的上限而不是那个默默扛事的长边。这也算是我刷题几年下来最值得分享的一个习惯。
盛最多水的容器：双指针优化与暴力枚举的数学证明
1. 为什么第一反应是枚举而枚举又行不通1.1 暴力解法的直觉从哪来第一次见到“盛最多水的容器”这道题几乎所有刷过 LeetCode 的人第一反应都是同一个把所有柱子两两组合算一遍面积取最大值不就行了两根柱子配一个容器暴力枚举所有(i, j)组合这个思路完全符合正常人的直觉没有任何弯弯绕绕。把题目翻译成人话给定一个非负整数数组height里面每个数字代表一根竖立在 x 轴上的柱子的高度。现在选两根柱子连同 x 轴一起围成一个“容器”问这个容器最多能装多少水。装水的多少取决于两个东西容器的高度由两根柱子中较矮的那根决定这就是木桶效应容器的宽度则是两根柱子在数组中的距离。于是面积公式非常直白S min(height[i], height[j]) * (j - i)暴力解法的代码也就三五行def max_area_bruteforce(height): n len(height) ans 0 for i in range(n): for j in range(i 1, n): ans max(ans, min(height[i], height[j]) * (j - i)) return ans逻辑没有毛病样例也能一眼跑对。但问题在于这个解法的复杂度是 O(n^2)而题目给出的数据范围通常到 10^5 级别。10^5 根柱子意味着大约 5 × 10^9 个组合要算这个量级在力扣的测评机上基本就是“提交即超时”的命运。1.2 暴力枚举的价值不是 AC而是定义搜索空间很多人刷题有个坏习惯看到暴力解会超时就直接跳过赶紧去背“最优解”。但暴力解其实有一个无可替代的价值——它完整地定义了这个问题的解空间。所有可能的容器组合就是一个巨大的上三角矩阵坐标(i, j)代表“以第 i 根柱子和第 j 根柱子为边界”的候选答案。暴力解做的事情就是把这个矩阵里的每一个格子都遍历一遍而任何更聪明的算法本质上都是在想办法少看一些格子并且还得保证“被跳过的格子里没有全局最优解”。“盛最多水的容器”真正的核心不是怎么枚举而是凭什么敢少枚举。这也是为什么这道题在 LeetCode 热门 100 题里的位置非常特殊它代码短但它逼着你思考一个硬核问题——如何证明一部份候选解可以安全丢弃。想明白这个问题比 AC 本身值钱得多。2. 双指针解法的核心短边才是真正的天花板2.1 从最宽状态出发为什么不能乱动既然暴力枚举行不通那就得找规律。先别急着想怎么优化我们把视角拉回面积公式$$S \min(h[L], h[R]) \times (R - L)$$一开始我们把两个指针放在数组的两端也就是L 0、R n - 1。这个状态的宽度是全局最大的。虽然两边高度不一定是最大的但宽度已经拉满了。下一步必然要让某个指针向内收缩因为两根柱子一旦选中容器范围就固定了不存在“向外扩”的可能性。问题变成向内收缩的时候动左边还是动右边这里就是整道题的灵魂所在。我们假设当前状态中h[L] h[R]也就是左边矮、右边高。现在有两种移动方式移动高的那一侧R 向左移动矮的那一侧L 向右。直觉告诉我们应该去动“看起来不重要”的那根。但很多人第一次做这题会下意识觉得“矮的那根是瓶颈我得换掉它”这个想法是对的也有人会想“高的那根更有潜力把它往里收一点说不定能遇到更均衡的组合”这个想法就是掉坑里了。2.2 移动长边为什么等于白走一步如果移动 R长边一侧由于 L 没变容器的高度依然被h[L]压着。而宽度(R - L)变小了。两个因子里面高度不可能超过原来的h[L]宽度又一定变小那面积怎么可能超过当前值用数学式子看更清楚。移动 R 到某个位置R且L R R$$S \min(h[L], h[R]) \times (R - L) \le h[L] \times (R - L) h[L] \times (R - L) S$$结论非常干脆只要移动长边新状态的面积严格小于当前面积。换句话说这一步绝对不可能刷新答案走了等于白走。2.3 移动短边为什么有机会翻盘反过来移动 L短边一侧就不一样了。虽然宽度同样变小了但新位置的柱子高度可能很高容器的高度不再被原来的短边锁死。一旦新的h[L]足够大面积就可能压过当前值。注意这里说的是“有机会”不是“一定”。移动短边也可能得到更小的面积但至少没有把可能性彻底堵死。所以双指针的移动策略就一句话每次都把较矮的那一侧往中间移动。如果两边高度相等动哪一边都可以原因后面会专门讲。这个策略的底层逻辑用一句话可以概括短边是当前容器真正的天花板任何以它为边的容器都不可能超过它现在贡献的上限所以该换的是它而不是那个还能继续扛事的长边。3. 严谨性检查凭什么说双指针不会漏掉最优解3.1 用“剪枝”的视角看指针移动背出双指针写法很简单但面试官真正想听的是“为什么这样移动不会错过最优解”。这一节我们把这个证明补上。假设当前指针位置是L和R并且h[L] h[R]。当前面积$$S h[L] \times (R - L)$$因为min(h[L], h[R]) h[L]所以面积就是左矮柱的高度乘以宽度。现在考虑任意一个以L为左边界、右边柱子k落在(L, R)区间内部的候选容器。不管k在哪新容器的高度都被min(h[L], h[k])限制住而这个值最多也只有h[L]同时宽度(k - L)严格小于(R - L)。于是$$S_k \min(h[L], h[k]) \times (k - L) \le h[L] \times (R - L) S$$也就是说所有以当前短边L为左边界的候选容器面积都不会超过当前这一轮算出来的面积。而当前面积在这一轮循环里已经更新进了ans。所以整行候选全部“废掉”可以放心地把L向右移一位不用担心丢掉最优解。h[R] h[L]的情况完全对称所有以R为右边界的候选容器面积都不会超过当前面积R向左移是安全的。3.2 相等高度时为什么移动哪边都对两边高度相等也就是h[L] h[R]时上面的两种论证同时成立。既可以说“所有以 L 为左边界的候选都不超过当前面积”也可以说“所有以 R 为右边界的候选都不超过当前面积”。因此代码里无论写left还是right--都能得到正确答案。这也是为什么网上各种题解在相等分支的处理上写得五花八门——有的用else left有的用else right--还有的用if...else覆盖相等情况结果都对。不是某个写法有隐藏 bug而是两边都安全。3.3 反证法一步到位如果觉得上面的“整行剪枝”说法不够有冲击力可以换一个反证法的表述。假设全局最优解存在于某个位置(L*, R*)并且我们的算法漏掉了它。那一定存在某次循环恰好L走到L*的位置、R还在R*的右边但此时我们把L*直接跳过了。这种情况只会发生在h[L*] h[R]或者相等时按代码选择了移动 L的前提下。而根据 3.1 的推导所有以L*为左边界、右边界在(L*, R)之间的候选容器面积都不会超过当前面积更不会超过当前维护的全局最大值ans。这就和“(L*, R*)是全局最优解”矛盾。漏不掉所以算法正确。这套证明的思路很值得记住。以后遇到别的双指针问题也可以照着这个模板写一遍先说明“某一侧的候选全都不优于当前值”然后理直气壮地移动指针。4. 完整推演标准用例从开头走到结尾4.1 一步步看指针怎么动理论说完了拿力扣自带的经典用例来跑一遍height [1, 8, 6, 2, 5, 4, 8, 3, 7]下标从 0 开始数组长度 9。按照“移动较矮一侧、相等时移动右侧”的策略完整过程如下表轮次LRh[L]h[R]宽度面积当前最大值谁在移动10817888L1 72188774949R8 73178361849R8 34168854049R相等5158441649R8 46148531549R8 5713822449R8 2812861649R8 6第 8 轮结束后 L 和 R 相遇循环终止最终答案是 49。4.2 这个推演暴露出的三个关键事实第一个事实最优解 49 在第二轮就已经出现了后面所有轮次的面积都小于它。这说明双指针不是“一步一步逼近最优解”而是一路在排除“不可能更优”的候选。最大值在哪一轮出现并不重要重要的是这一轮一定会被遍历到。第二个事实这个用例里 8 号柱下标 1异常地高导致它一整路都在当“长边”右边的指针一路收缩到它旁边。这种“一边倒”的情况很常见恰恰说明剪枝的效率——如果某根柱子一直是当前最矮边外侧的高柱另一侧会快速扫过中间大量无效区域。第三个事实如果相等时改成移动 L结果依然是 49。不信你可以自己按表格改一遍在第 4 轮选择移动 L后续路径会切换到以 6 号柱下标 6为右边界的剪枝过程但最终最大值不变。这就是上一节证明的“相等两边都安全”在真实数据上的验证。5. 代码落地Java、Python、C 实现与细节5.1 三种常用语言的版本Java 版本国内面试写的最多class Solution { public int maxArea(int[] height) { int left 0, right height.length - 1; int ans 0; 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 版本刷题时用来快速验证思路def max_area(height): left, right 0, len(height) - 1 ans 0 while left right: area min(height[left], height[right]) * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ansC 版本竞赛选手的最爱class Solution { public: int maxArea(vectorint height) { int left 0, right height.size() - 1; int ans 0; while (left right) { int area min(height[left], height[right]) * (right - left); ans max(ans, area); if (height[left] height[right]) { left; } else { --right; } } return ans; } };先算面积、再更新答案、最后移动指针这个顺序不要乱。如果把指针移动写在面积计算前面第一轮就会漏掉L 0, R n - 1这个初始状态答案会错。5.2 复杂度为什么是 O(n) 而不是 O(n 的一半) 之类时间上两个指针从两端出发相向而行每轮只移动一个指针每个元素最多被指针扫过一次所以是 O(n)。空间上只用了两个整型变量O(1) 额外空间。这个复杂度基本就是本题的最优了。虽然从“读数组”的角度看你至少得把所有柱子高度看一遍才知道最高峰在哪所以 O(n) 的下界很自然。双指针真正牛的地方在于它没有用排序、没有用哈希表、没有开额外数组就在原数组上扫地一样走了一遍把 O(n^2) 的搜索空间压缩成了 O(n)。6. 容易翻车的几个点以及我实测过的微优化6.1 五个高频错误现场第一个错误是移动方向写反。有人会把比较条件和指针移动写岔if height[left] height[right]: right - 1 else: left 1这就等于每次都在移动长边面积只会越算越小最优解直接被跳过。用前面的用例跑一遍可以得到 40 甚至别的错误答案。这个错误背后的心理动因很有意思有人误以为是“矮边限制了高度我要把矮边保留住”但实际上保留矮边等于保留了天花板真正该换的就是矮边。第二个错误是循环条件写成left right。左右指针相遇时宽度为 0算出来的面积也是 0不影响最终结果但白白多算一轮。更重要的是逻辑上不够干净写完自己看着也别扭。这个题while (left right)是正解。第三个错误是忘记取最小值。有人直接把height[left] * height[right] * (right - left)当面积这是拿两根柱子拼矩形不是装水。容器能装多少水取决于短板不取决于长板。第四个错误是更新答案的时机不对。先移动指针再算面积会漏掉第一轮的初始最大宽度状态先移动指针再更新ans还可能把中间某些有效状态漏掉。正确顺序就是上面代码里那样算面积 - 更新答案 - 移动指针。第五个错误是忽视数组太短的健壮性。题目保证了height.length 2但如果你把这段代码抽出来做工具函数最好加一行判空和长度判断if height is None or len(height) 2: return 06.2 要不要做“跳过更矮柱子”的优化网上有些题解会在移动指针之后加一个 while 循环跳过所有“不高于当前短边”的柱子写成这样def max_area_optimized(height): left, right 0, len(height) - 1 ans 0 while left right: h_left, h_right height[left], height[right] ans max(ans, min(h_left, h_right) * (right - left)) if h_left h_right: left 1 while left right and height[left] h_left: left 1 else: right - 1 while left right and height[right] h_right: right - 1 return ans这个优化的逻辑是既然刚刚已经确认“以当前短边为边界的候选都不会超过当前面积”那移动之后如果新位置的高度还不如原来的短边它更加不可能翻盘可以继续跳。推导是成立的但这个优化在力扣的测试数据上收益非常有限。原因很简单基础版本来就是 O(n)100000 个数据点跑一遍只要几十毫秒你再怎么跳也不可能跳出量级级别的差距。我的实测建议是日常刷题和面试写基础版就够了代码可读性最好不容易写错。跳跃版可以作为思维练习自己推导一遍理解它为什么安全但没必要背下来。真到了面试现场你花 30 秒写基础版再用 30 秒把剪枝证明讲清楚比甩一个加了三个 while 的“优化版”有用得多。7. 从盛水容器到对撞指针一类题目的通用思考框架7.1 把候选解想象成矩阵双指针就是在消行消列学到这如果只把“盛最多水的容器”当成一道题来记那有点亏。它真正的价值是提供了一个可以迁移到很多问题上的思考框架。前面提到所有候选解可以看成一个上三角矩阵横坐标是左指针纵坐标是右指针。双指针每移动一次其实是在消掉一整行或者一整列。为什么复杂度是 O(n)因为从右上角走到左下角这个过程最多消 n 行加 n 列总共 2n 步封顶。这个“矩阵消行消列”的视角我后来在很多对撞指针题里都用得上。拿到新题先画出候选矩阵然后问自己当前这一步我有没有一个铁的理由能说明某一行或某一列不可能包含最优解如果能双指针就成立了。7.2 同类题怎么套这个框架LeetCode 上有一串题本质都是对撞指针第 167 题“两数之和 II - 输入有序数组”当前和大于 target 时右指针左移是安全的因为左指针已经是最小值和它配更小的数只会更小第 15 题“三数之和”固定一个数后剩余区间用对撞指针依据是排序后的单调性第 16 题“最接近的三数之和”同样是对撞加绝对值比较第 42 题“接雨水”表面上是另一套逻辑但核心直觉“哪边矮就从哪边开始算”与本题如出一辙第 611 题“有效三角形的个数”固定最长边之后用对撞指针统计排除依据是两边之和大于第三边。这些题都有一个共同点都可以先从暴力枚举出发然后找到一个严格的“指针移动依据”把搜索空间砍半再砍半。而“盛最多水的容器”是所有这类题里移动依据最容易讲清楚、证明最简短的一道。所以刷 LeetCode 热门 100 题的时候我强烈建议把这一题放在双指针专题的第一位先把证明啃下来后面一串题都会顺很多。我个人刷这题的经验是AC 只是及格线真正的收获在于能合上答案用五分钟时间把“为什么移动短边不会漏解”完整推一遍。你能在白板上把这个证明写出来这道题才算真正属于你了。后续做接雨水、三数之和的时候我经常还会绕回这个证明来找手感——短边是天花板该换的是一个容器的上限而不是那个默默扛事的长边。这也算是我刷题几年下来最值得分享的一个习惯。