LeetCode 热题 100 里有一道很特别的问题11. 盛最多水的容器。说它特别是因为代码量短到可以瞬间背下来但真正能把双指针方案为什么正确讲清楚的人反而不多。我第一次做这题时老老实实写了双层循环一提交直接超时后来照题解把双指针背了下来面试被追问“为什么移动矮的那根柱子”时当场卡住。这篇笔记想把这道题彻底掰开揉碎讲明白从暴力解出发一步步推演到双指针再把正确性证明、边界情况、提交时踩过的坑全部过一遍。适合刚开始刷题的小白也适合想在面试中把思路讲得有层次的人。1. 题面拆解与暴力解法先搞清楚面积公式1.1 一句话说清面积公式题目给你一个非负整数数组height数组里的每个数字代表一根垂直于 x 轴的柱子高度下标就是这根柱子的 x 坐标。要你找出两根柱子让它们和 x 轴围成的区域能盛下的水最多。这里有个生活常识要先点破一个容器能装多少水取决于短板。所以两根柱子 i 和 j 之间的盛水面积不是height[i] * (j - i)而是S(i, j) min(height[i], height[j]) * (j - i)高度取两根柱子的较小值宽度是下标的差。题目要的就是这个S(i, j)的最大值。原题示例[1,8,6,2,5,4,8,3,7]的答案是 49对应下标 1 的柱子和下标 8 的柱子高度取min(8, 7) 7宽度是8 - 1 7面积正好是7 * 7 49。到这里题目本身没有任何玄机纯粹是求一堆点对里面积的最大值。1.2 暴力枚举最直接的思路和它的上限最容易想到的方案就是枚举所有两根柱子的组合。两层循环外层固定左柱子 i内层枚举右侧所有柱子 j计算面积并更新最大值。def max_area_bruteforce(height): n len(height) ans 0 for i in range(n): for j in range(i 1, n): area min(height[i], height[j]) * (j - i) ans max(ans, area) return ans这段代码逻辑完全正确小规模用例也能得到正确答案。但问题是它的时间复杂度是 O(n^2)。当 n 达到 10^5 级别时总比较次数在 10^10 左右现代计算机跑这个数量级的纯循环也有明显压力。LeetCode 的判定数据不会让你用暴力解法轻松通过它存在的意义恰恰是让你意识到“必须优化”。遇到这类求最值的问题第一步先把暴力解写出来不是为了提交而是为了确认自己对题面的理解没有偏差。暴力解是很好的“对照答案”后面写出高效解法后可以用小数据量跑一遍两个结果对得上才放心。1.3 为什么要优化数据规模带来的真实压力原题约束里 n 最大到 10^5这意味着任何 O(n^2) 的做法都会在大数据上超时。面试里聊这题通常也默认你要给出 O(n) 或 O(n log n) 级别的方案。O(n log n) 当然也能接受但这道题更漂亮的解法是 O(n)而且只需要 O(1) 额外空间也就是常说的“双指针”。为什么能用双指针核心在于面积公式存在单调性特征向内移动指针会让底边变短除非高度变大到足以补偿否则面积不会增加。这个特征给了我们用“排除法”不断缩小搜索范围的可能。2. 双指针优化思路为什么每次移动矮的那根2.1 从“底边变短”想到“短板翻盘”假设数组长度是 n初始情况我们让一个指针 left 指向最左边下标 0另一个指针 right 指向最右边下标 n - 1。此时底边是最长的也就是right - left最大。如果从这个状态向内移动指针无论移动哪边底边right - left都会变小。所以想让面积比当前值大唯一的希望是“高度”涨上来。但高度是取两个端点的较小值真正决定高度的是那个矮的端点。这里就有个直觉判断既然短板决定了高度那我把长板往内挪高度不会变高把短板往内挪新端点可能比原来高面积才有机会变大。这个直觉是对的但面试官不会只听直觉所以要把数学推导补上。2.2 核心推导为什么敢于丢弃矮的一侧我们分析一种情况当前 left iright j且height[i] height[j]也就是左端点矮。先计算当前面积S(i, j) height[i] * (j - i)对于任意一个同样以 i 作为左端点、右端点 k 落在 i 和 j 之间的组合面积是S(i, k) min(height[i], height[k]) * (k - i)因为min(height[i], height[k]) height[i]同时k - i j - i所以一定有S(i, k) S(i, j)这说明什么说明只要左端点还是 i它和内侧任意右端点组合出来的面积都不可能超过当前(i, j)这个组合。既然当前位置已经算出了“以 i 为左端点的最大可能面积”而且这个面积已经被记录到答案里那么之后左端点 i 就再也没有保留价值了。可以放心地把 left 向右移动一位丢弃 i。反过来如果height[i] height[j]也就是右端点矮那么固定右端点 j 时任意内侧左端点 k 与 j 的组合面积都小于当前面积于是可以把 right 向左移动一位。这个推导就是双指针方案的核心。它不是在猜而是通过严格的数学关系说明每一次移动都是在删除一批不可能成为最优解的候选区间。2.3 完整正确性证明排除法确定不漏解有人会担心你这样一次次排除万一最优解区间在中间某个位置还没被检查到就被跳过了怎么办答案是不会。我们用排除法的思路来理解。算法维护的搜索范围是所有可能成为答案的区间集合。每一步我们基于当前两个端点的高低关系证明了某个端点和所有内侧端点组成的区间都不可能是最优解。于是这个端点被删除搜索范围缩小。比如height[i] height[j]时我们证明的是“以 i 为左端点的所有区间”都无法超过当前区间因此删除左端点 i 不会伤及还没考虑的最优解。因为任何包含 i 的区间都已经在上一步被证明不如当前区间了而当前区间的面积已经保存在 ans 里。全局最优解要么是当前区间要么在剩余区间里所以删除 i 后仍然覆盖所有可能性。整个过程不断收缩左右边界直到两个指针相遇。每一步删除的都是“已排除的候选”剩下的搜索空间始终包含全局最优解。等到循环结束时ans 自然就是最大值。如果两个端点高度相等即height[i] height[j]移动哪边都一样因为无论固定左端点还是固定右端点都能用同样的不等式证明内侧组合不会超过当前面积。代码里通常写成移动右指针只是习惯不是必须。3. 最终代码实现与编码细节Python、C与边界处理3.1 Python实现最短路径到正确答案def maxArea(height): 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 ans核心逻辑就一个 while 循环。每次计算当前两根柱子的面积更新答案然后比较两个端点的高度移动较矮一侧的指针。很多初学者最容易写错的地方是把更新 ans 的语句放错位置或者忙了半天忘记在移动前计算面积导致结果偏小。还有一个小细节if height[left] height[right]: left 1 else: right - 1这段代码在两端高度相等时会移动右指针。前面已经说过相等时移动哪边都正确所以这样写没有任何问题。3.2 边界条件与健壮性处理LeetCode 原题保证数组长度至少为 2所以代码里不需要显式判空。但在工程化写法里函数应该具备自我保护能力。比如传入空数组或者长度为 1 的数组时直接返回 0 会更合理因为至少需要两根柱子才能围成容器。def maxArea(height): if not height or len(height) 2: return 0 # 后面逻辑不变还有就是全 0 数组的情况比如[0, 0, 0, 0]任何两根柱子组成的面积都是 0代码会正常返回 0。这些边界情况在面试的时候主动提一下是很加分的细节。循环条件的写法也要注意。while left right是正确的因为当 left 和 right 指向同一根柱子时宽度为 0没有计算意义。如果写成while left right等于多做一次无效计算虽然不影响结果但显得不够严谨。3.3 C/Java版本与溢出注意事项C 写法和 Python 基本一致但有一个值得展开的点面积计算会不会溢出。原题约束 n 最大 10^5height 里单个元素最大 10^4所以面积理论上限大约是 10^4 * 10^5 10^9。这个数值在 C 的 int 范围内因为 int 最大值约 2.1 * 10^9。用 int 提交也不会出事。但我在实际刷题时更倾向于用 long long 保存中间结果原因是很多变体题会放宽数据范围。比如 n 放大到 10^6面积就可能轻松超过 int 上限。用 64 位变量写出来的代码即使题目数据变化也不会留下隐患。class Solution { public: int maxArea(vectorint height) { int left 0, right height.size() - 1; long long ans 0; while (left right) { long long h min(height[left], height[right]); long long area h * (right - left); if (area ans) ans area; if (height[left] height[right]) { left; } else { --right; } } return (int)ans; } };Java 版本同理用 long 保存 ans最后强转 int 返回。LeetCode 的判题系统不会因为你用 long 而扣分反而显得更有经验。4. 实战排坑这几个错误提交我全都踩过4.1 高频错误对照表我当年做这道题时前几次提交无一例外都挂在细节上。这里整理一份高频错误对照表很多坑没有实际跑过根本想不到。症状可能原因解决办法答案偏小计算面积放在移动指针之后先算面积再移动指针运行超时用了 O(n^2) 暴力双层循环改用双指针 O(n) 解法返回 0循环写成 while left right最后 left 和 right 相等时宽度为 0改用 while left right面积结果溢出高度乘以距离超过 int 上限中间变量用 long long / long数组为空时崩溃没有判空直接访问 height[0]函数开头加空数组判断结果不稳定两端高度相等时移动指针逻辑混乱记住相等时移动任意一边均可看起来都是小问题但面试现场时间紧张很容易在这种地方翻车。我的习惯是写完代码后先用一个示例手推一遍流程确认每一步指针和 ans 的变化再提交。4.2 手推几个边界用例拿示例数组[1,8,6,2,5,4,8,3,7]手推初始 left0right8height[0]1height[8]7面积1 * 8 8。左边矮left 移到 1。此时 left1right8height[1]8height[8]7面积7 * 7 49更新 ans49。右边矮right 移到 7。之后无论指针怎么移动宽度都在变小面积很难再超过 49。最终返回 49与题目一致。再看几个特殊用例[1,1]面积是1 * 1 1代码正常返回 1。[1,2,1]left0right2面积1 * 2 2左矮left 移到 1leftright 退出返回 2。实际最大也是 2正确。[2,3,4,5,18,17,6]最大面积应该出现在下标 1 的 3 和下标 5 的 17 之间面积3 * 4 12不对让我重新算height [2,3,4,5,18,17,6]最大面积是下标 3 的 5 和下标 5 的 17宽度 2高度 5面积 10下标 4 的 18 和下标 2 的 4宽度 2高度 4面积 8两个端点 2 和 6宽度 6高度 2面积 12。所以最大是 12。双指针从两边收拢时会记录到 12没问题。手推用例的目的不是一个个背下来而是验证自己的代码逻辑没有系统性偏差。4.3 面试现场讲这题的正确姿势面试遇到这题不建议上来就甩双指针代码。比较稳的讲解节奏是这样的先说暴力做法枚举所有点对O(n^2)确认题面理解正确。然后说“我发现了面积公式里的单调性”解释为什么移动矮的一端是安全的。如果面试官追问就把前面第 2 节的不等式推导讲清楚。最后给出代码分析时间复杂度 O(n)、空间复杂度 O(1)。我自己在面试里吃过亏当时直接写了最优解面试官反而问“你怎么知道这样不会漏掉最优解”我一时答不上来。后来才明白这题考察的正是你能否证明自己的优化是安全的。能讲明白证明比光写出代码有价值得多。5. 从这一题看一类“双指针收缩”问题5.1 和接雨水的区别到底在哪很多人刷题时会拿“盛最多水的容器”和“接雨水”对比因为它们都涉及柱子、下标差和水看起来很像。但两道题的核心思想有本质区别。本题求的是“两根柱子围成的容器最大面积”只有两条边水量取决于短板乘以底边。接雨水求的是“下雨后能接住多少水”每根柱子上的水量由它左右两侧最高柱子的较小值决定需要累加所有凹陷处的积水量。代码细节上差异也很大。本题双指针移动的是“较矮的那侧”接雨水的双指针则要维护左侧最大值和右侧最大值哪边的最大值更矮就从哪边结算当前位置的水量。如果只背模板很容易把两题的指针移动逻辑搞混。5.2 三数之和也是同一套路双指针收缩的经典套路还有“三数之和”。那道题先对数组排序然后固定一个数剩下的区间用双指针寻找两数之和。指针移动的依据是当前和与目标值的大小关系和大于目标值就右指针左移和小于目标值就左指针右移。和盛水容器这题放在一起看会发现共同套路利用数据本身的顺序或单调性每一步都能排除一批不可能的解从而把暴力枚举的 O(n^2) 甚至 O(n^3) 降到 O(n) 或 O(n^2)。所以刷题时不要孤立地背某一道题而是把“双指针收缩”当成一类工具。遇到能用排除法缩小搜索范围的问题时优先思考这个工具是否适用。5.3 什么信号提醒你“该用双指针了”根据我刷题的经验出现以下特征时通常可以考虑双指针问题涉及数组或字符串并且要求连续区间内的某种属性暴力解法是 O(n^2) 的区间枚举区间端点向内收缩时计算结果存在单调性要求空间复杂度 O(1)不能用哈希表或额外数组盛水容器完美命中这些特征区间是两根柱子围成的范围暴力枚举所有点对移动矮侧指针有严格的数学保证额外空间只需要两个变量。从这道题开始理解双指针再迁移到接雨水、三数之和、最长回文子串等问题会比刷十道题但每道只看题解有效得多。我自己反复做这道题至少三遍。第一遍背代码第二遍推证明第三遍才开始真正理解“移动矮的”背后的排除逻辑。现在再遇到类似的双指针题目我会先问自己这一步排除的候选集到底是什么它为什么不可能成为最优解想明白这个问题代码反而只是顺手写出来的东西。如果你也在这题上卡过或者面试时被“为什么不会漏”问住希望这篇笔记能帮你把这层窗户纸捅破。算法学习有时候真的不是看多少遍题解的事而是需要在某个瞬间把每个不等式都自己推一遍。