1. 题目全貌与直觉破题先弄懂面积公式里藏着什么1.1 这题到底在问什么先说人话版理解。给你一个数组 height里面每个数字代表一根柱子的高度柱子宽度是 1两根柱子之间的水平距离就等于它们下标的差值。现在让你挑两根柱子当容器壁往中间倒水问最多能装多少水。真正要算的其实就是一句话选两个下标 i 和 ji j装水量 min(height[i], height[j]) × (j - i)。为什么取最小值因为水会从矮的那边漏出去这是物理常识放在题目里就是最朴素的限制条件。我看到不少初学者卡在这道题上的第一反应都是这不就是枚举吗两层循环全组合统统算一遍取最大值完事。对数据量小的时候确实完事。但 LeetCode 的测试数据不会给你这么温柔的上限高度数组的长度轻松给到 10 万级别。这时候暴力枚举的 O(n²) 复杂度就彻底顶不住了10 万根柱子两两组合差不多是 50 亿个配对单线程跑下来要按分钟算最后只能乖乖收获一个 Time Limit Exceeded。所以这道题真正考察的东西不是你会不会套面积公式而是你有没有能力从“全量枚举”的思维定势里跳出来找到一种不用穷举所有配对、但依然保证不错过最优解的算法。这个算法就是标题里的主角——双指针。1.2 别急着写代码先把暴力解的死因分析清楚暴力解的死因在于它做了太多无用功。举个例子假如数组是 [5, 9, 2, 6]你枚举 i0、j3 这个组合时面积是 min(5,6)×3 15没问题。但与此同时你还会算出 i0、j1i0、j2i1、j2i1、j3i2、j3 这一堆结果其中绝大多数跟最优解根本一点关系都没有。真正值得思考的是在我们已经知道 i0 这根柱子只有 5 高的前提下它跟 j1高度 9、j2高度 2、j3高度 6这三根柱子配对面积公式里真正决定高度上限的是什么是 5也就是 i0 这侧的高度。因为不管右侧柱子多高容器能装的水面最高只能到矮的那根——5 的高度。也就是说当右侧柱子越往左靠、水平距离越短时面积反而越小。这里就暴露了一个可以被利用的规律一旦确定了某一侧是短板那么这根短板跟更远处的柱子配对的面积会随着距离缩短而严格减小。既然面积只会更差那这些配对状态就根本不需要计算。怎么高效地把这些“必不可能最优”的状态批量扔掉就是双指针算法的出发点。2. 双指针的贪心策略凭什么移动矮的那一侧是安全的2.1 从两端向中间收缩的操作方式双指针在这道题里的做法非常直观一个指针 left 指向数组最左边一个指针 right 指向最右边先算这两根柱子围成的面积记录当前最大值。然后比较 height[left] 和 height[right] 谁矮把矮的那一侧指针往中间移动一步再算新的面积更新最大值。重复这个过程直到两个指针相遇。这看起来就是一个非常简单的循环但很多人背下了代码却讲不清楚“为什么移动矮的那一侧”。面试时如果被追问一句“为什么不能移动高的那一侧”卡壳的人不在少数。所以这一节我们从头推导一遍。当前状态是 left iright j且假设 height[i] height[j]也就是说左侧是矮柱子。此时面积等于 height[i] × (j - i)。我们的选择有两个移动 left或者移动 right。移动 left 意味着新的状态是 (i1, j)移动 right 意味着新的状态是 (i, j-1)。注意不管移动哪一侧新状态的水平距离都是 (j - i - 1)一定比原来小 1。也就是说宽度一定会减少。既然宽度必然减少想让面积变大唯一的机会就只能寄托在高度上。但这里有个关键约束新面积的高度还是由两根柱子中的矮者决定的。如果移动的是高柱子 right右侧新柱子无论多高容器的高度上限依然被左侧 height[i] 锁死也就是说高度最多还是 height[i]甚至可能更矮。于是新面积的最大可能值是 height[i] × (j - i - 1)严格小于当前面积 height[i] × (j - i)。这意味着移动高柱子一定会让面积变小没有任何翻盘的可能。但如果移动的是矮柱子 left情况就完全不同了。左侧新柱子如果变高了容器的高度上限就可能被抬升新面积就有了超过当前面积的机会。极端情况比如 height [5, 100, 1, 100]初始 left0、right3height[0]5、height[3]100当前面积是 5×315。移动矮侧 left 到下标 1 后height[1]100新面积是 100×2200直接翻了十倍。移动高侧 right 则永远等不到这个结果。所以策略很明确哪边矮就动哪边。这个策略本质上是贪心思想——每一步都选择“有可能让结果变好”的方向移动而对“已经证明必然变差”的方向直接放弃。2.2 手动走一遍经典用例亲眼看看指针如何逼近最优解光说理论有点干我们拿这道题的官方示例数组 [1, 8, 6, 2, 5, 4, 8, 3, 7] 完整走一遍。初始 left0right8height[left]1height[right]7面积 1×8 8。最左边这根柱子高度只有 1它跟任何柱子的配对的面积都不可能超过 1 乘以它们之间的距离而当前距离 8 已经是最大距离了所以它铁定不是最优解的一部分移动 left。第二轮 left1right8。height[left]8height[right]7右侧矮面积为 7×749。此时右侧这根高度 7 的柱子与 left 左侧任意柱子的配对距离都小于 7而且高度上限最高也就是 7甚至更矮因为左侧下标 0 的柱子高度只有 1但当前讨论的配对里左侧还有其他选择不过距离都在缩小所以右侧指针贡献的最优状态已经被我们拿下了。移动 right。第三轮 left1right7。height[left]8height[right]3左侧矮面积 8×648。虽然比 49 小但还是要更新判断。移动 left。第四轮 left2right7。height[left]6height[right]3右侧矮面积 3×515。移动 right。第五轮 left2right6。height[left]6height[right]8左侧矮面积 6×424。移动 left。第六轮 left3right6。height[left]2height[right]8左侧矮面积 2×36。移动 left。第七轮 left4right6。height[left]5height[right]8左侧矮面积 5×210。移动 left。第八轮 left5right6。height[left]4height[right]8左侧矮面积 4×14。移动 left。此时 left6、right6两指针相遇循环结束。整个过程遍历下来最大面积定格在第二轮得到的 49也就是下标 1 和下标 8 这两根柱子高度 8 和 7围成的容器。整个数组 9 个元素我们只算了 8 次面积就把最优解找出来了。而暴力枚举需要算 36 次。数据规模越大这个差距越恐怖。2.3 严格论证被排除的状态为什么不可能藏着最优解如果你只停留在“矮侧移动有机会变好”的直觉层面面试时还是容易被追问到细节。真正严谨的表述是这样的当处于状态 (i, j) 且 height[i] height[j] 时对于任意的 k 满足 i k j考虑状态 (i, k)。它的面积是 min(height[i], height[k]) × (k - i)。由于 k-i j-i而且 min(height[i], height[k]) ≤ height[i]所以这个面积一定 ≤ height[i] × (k-i) height[i] × (j-i)。后者恰恰就是状态 (i, j) 的面积。这就说明一旦我们确定了 height[i] 是当前的矮侧那么以 i 为左端的所有尚未考察的状态 (i, k)面积全部严格小于当前状态。换句话说左指针 i 已经不可能再和其他任何柱子组合出超过当前面积的结果了把它右移一位是一个绝对安全、不会丢失最优解的操作。同理当 height[i] ≥ height[j] 时注意相等的情况可以归入这一类也可以任选一侧不影响结论以 j 为右端的所有未考察状态面积都不可能超过当前状态右指针左移是安全的。这就是双指针算法正确性的完整证明每一步都在“批量排除不可能状态”所有被跳过的区域都有数学上严格的面积上界因此最终收敛到的最大值必然是全局最优解。这个证明并不复杂但它的价值在于让你从“记住这个解法”进阶到“理解这个解法为什么对”。3. 代码实现与边界处理从思路到一份能直接提交的版本3.1 最简双指针实现Python 版思路理通了代码反而简单。下面这份 Python 实现是我在实际刷题时用的版本可以直接复制到 LeetCode 的编辑器里提交def max_area(height): left 0 right len(height) - 1 max_water 0 while left right: width right - left if height[left] height[right]: h height[left] left 1 else: h height[right] right - 1 max_water max(max_water, width * h) return max_water这个实现有一个微小但值得注意的设计先移动指针再更新最大值。我见过不少人的写法是先算完面积更新最大值再倒腾指针本质一样但如果把移动逻辑和面积计算搅在一起代码可读性会差一些。我更推荐用变量 h 先把当前容器高度取出来再统一做 max 比较这样逻辑链路短不容易漏算。核心部分其实只有五件事两个指针初始化为数组两端left0rightlen(height)-1。循环条件是 left right指针相遇即停止因为单根柱子无法构成容器。每次计算当前容器宽度 width right - left。取矮柱子的高度作为容器有效高度并移动矮侧的指针。用 width * h 更新全局最大值。如果你用的是 C 或 Java思路完全一致只是语法层面多注意一下数组越界。这里我顺手给一个 C 版本作对照int maxArea(vectorint height) { int left 0; int right height.size() - 1; int maxWater 0; while (left right) { int width right - left; int h; if (height[left] height[right]) { h height[left]; left; } else { h height[right]; right--; } maxWater max(maxWater, width * h); } return maxWater; }两个版本的逻辑完全一致你只需要记住一套思想在任何语言里都能落地。3.2 三个容易踩的细节坑第一个坑循环条件写成了 left right。这会导致两指针指向同一个位置时再算一次面积宽度为 0面积是 0不会影响结果正确性但多一次无意义计算。问题不大但面试官如果较真会觉得你的边界处理不够干净。标准写法是 left right。第二个坑误把高度比较方向记反。有人写着写着就变成了“移动高的一侧”理由是“高柱子是瓶颈的相反面”。这个方向一旦反了算法就退化成 O(n²) 级别的无意义遍历甚至直接错解。因为移动高侧会系统性丢弃所有潜在更优状态。我在脑内排查代码时会反复默念矮决定水面高度为了提升水面只能替换矮侧所以移动矮侧。第三个坑相等高度时的判断分支。当 height[left] height[right] 时我的代码走的是 else 分支移动右指针。其实移动左指针也完全正确。理论依据是两柱等高时无论移动哪一侧当前面积都已经成为以这两侧为端点组合里的最大值上限两边都不可能有更好的配对所以任选一侧丢弃即可。但实际刷题时我建议保持一个固定的相等处理策略不要一会左一会右免得自己在 debug 的时候混乱。3.3 从这道题抽象出的对撞型双指针模板做完这道题你会发现双指针可以提炼成一个万用骨架初始化两个指针到数据两端left0, rightn-1 while left right: 依据题意计算当前状态的结果并更新最优值 根据题目约束决定移动左侧或右侧指针 return 最优结果关键就在于第三步“根据题目约束决定移动哪一侧”这道题里是移动矮侧三数之和里是根据目标和与 0 的大小关系决定移动左指针还是右指针二分查找本质也是这个骨架。你只要练熟了这种“对撞型”双指针的状态排除思维它能覆盖的题目非常多。4. 复杂度分析与正确性验证如何确认这版代码是真的稳4.1 这两个数字O(n) 时间和 O(1) 空间双指针解法的时间复杂度是 O(n)因为 left 和 right 两个指针加起来最多移动 n 次每次移动都只做常数级别的运算循环的总执行次数不会超过数组长度。空间复杂度是 O(1)只用了几个固定变量没有额外的数组、哈希表或递归栈。用暴力枚举做对比两者的差距在数据量 10 万时就已经是秒级和分钟级的差别了。LeetCode 上这道题官方给出的数据范围是 n 最大到 10^5O(n) 解法稳过O(n²) 解法必超时。所以看到这种“最大面积 / 最大距离 / 最长和”类问题优先想双指针和滑动窗口基本方向不会错。4.2 边界用例自测清单提交代码之前我习惯先用几组边界用例自己过一遍确认不会翻车。你可以在本地或者 LeetCode 的 Playground 里快速测试用例期望输出说明height [1]0只有一根柱子无法形成容器height [1, 1]1两根等高的最短组合宽度 1高度 1height [1, 2, 1]2两侧高、中间矮的代表性用例最优是左右两端height [4, 4, 4, 4]12全部等高的极端情况面积只取决于最远距离height [0, 0, 0]0全零值的边界任何面积都为 0height [1, 8, 6, 2, 5, 4, 8, 3, 7]49官方示例必须能和手工推导对上我自己最担心的是 [1, 2, 1] 这类用例因为手动模拟时指针移动只有两步正好能暴露“移动方向选错”的问题。如果你把代码改成移动高侧在这个用例上答案会变成 1正确值是 2一眼就能发现问题。4.3 用对拍脚本暴力验证双指针的正确性光靠几个手工用例不够我还有一个更扎实的验证办法写一个暴力解法作为参考实现再用随机数据把双指针解法和暴力解法对拍。这是刷算法题时验证复杂算法正确性的通用手段尤其是贪心、双指针这类“听起来有道理”的算法对拍能帮你揪出隐藏的逻辑漏洞。import random def max_area_brutal(height): n len(height) ans 0 for i in range(n): for j in range(i 1, n): ans max(ans, (j - i) * min(height[i], height[j])) return ans def max_area_two_pointer(height): left, right 0, len(height) - 1 ans 0 while left right: width right - left if height[left] height[right]: h height[left] left 1 else: h height[right] right - 1 ans max(ans, width * h) return ans for _ in range(1000): n random.randint(1, 20) arr [random.randint(0, 10) for _ in range(n)] if max_area_brutal(arr) ! max_area_two_pointer(arr): print(发现不一致:, arr) break else: print(1000 组随机数据全部通过)这种随机化对拍的本质是小数据量下暴力枚举绝对正确如果双指针在小数据上也和暴力解完全一致那它在大数据上的正确性就有了强有力的佐证。配合前文的逻辑证明代码的正确性可以做到双重保险。5. 双指针的通用套路与面试延伸从这一题到一整类题型5.1 双指针的两种常见形态通过盛水容器这道题你已经掌握了所谓的“对撞型”双指针。面试和比赛中常见的双指针还有另一种形态——“快慢型”也就是两个指针都从左侧出发一个走得快一个走得慢典型应用是链表找环和数组去重。对撞型双指针的识别特征非常明确问题要求在数组的两端做选择需要两端往中间收缩来遍历所有“状态”并且存在某个数学依据证明某一侧的状态可以批量排除。盛水容器是移动矮侧三数之和是“和小于 0 就左移、大于 0 就右移”接雨水的双指针解法是“哪侧当前最大高度更矮就处理哪侧”。这几道题如果放在一起刷你会发现底层逻辑完全一致都是“用已知信息安全地缩小搜索空间”。5.2 双指针和滑动窗口到底什么关系我经常被问到的一个问题是双指针和滑动窗口是不是一回事。严格来说它们是近亲但不完全相同。滑动窗口通常关注的是一个连续区间内部的某种性质窗口左右边界都只能单向移动一般用在一个区间里求最长/最短/满足条件的子数组这类问题。对撞型双指针关注的是两个端点配对的整体最优值左右边界对向移动。一个很实用的区分方法如果题目问的是“子数组 / 连续区间的某某性质”优先想滑动窗口如果题目问的是“选两个元素、配对、最优”而且元素顺序本身有意义优先想对撞型双指针。盛水容器问的是“选哪两根柱子”自然落入后者。5.3 面试官可能顺着这道题追问的变化这道题在面试里出现的频率极高而且面试官几乎不会只让你写完代码就放过你。我见过的高频追问大概有这么几种。第一个追问如果数组里存在高度为 0 的柱子会影响算法吗不影响高度为 0 时 min(...) 的结果是 0面积是 0移动指针的逻辑照常执行算法正确性不受影响。第二个追问如果数组长度是 1 或者 0应该返回什么返回 0因为没有两根柱子就构不成容器。注意循环条件 left right 天然处理了这种情况不需要额外写判断。第三个追问如果要同时输出最大面积对应的两根柱子下标代码怎么改这就需要在更新 max_water 的地方同步记录 left 和 right 的快照。注意指针在更新之后才移动所以记录下来的下标是移动前的。这也是一个很好的测试你是否真正理解指针移动时机的设计题。第四个追问如果把问题扩展到选三根柱子求最大盛水量比如经典的“接雨水”问题双指针思路还能不能用答案是能但要换个角度不再是两两配对看距离而是对于每个位置它的积水高度取决于左右两侧最大高度的较小值。这时候双指针的移动依据会变成“哪一侧当前最大高度更小就处理哪一侧”。整个思维模型仍然是从两端向中间收缩只是排除状态的依据不同了。我在实际刷题过程中最大的体会是盛水容器这道题最容易犯的错误恰恰是代码写得太顺——因为模板太简单导致很多人没有认真思考每一步指针移动背后的排除逻辑结果换一个类似但略有变化的题目比如要求输出最优解的下标或者面积相同的时候要取哪一组就卡住了。建议你在写完这题之后关掉题解在纸上用三个不同的数组手动模拟一遍指针移动过程并自问一句我这一步移动到底排除了哪些状态为什么它们不可能是最优的能把这个问题回答清楚你才是真的掌握了这道题。