力扣热题100里的“盛最多水的容器”大概是我见过的双指针题目里最优雅的一道。它没有复杂的递归没有晦涩的动规最终通过的代码撑死也不超过15行但就这不到15行的逻辑当年让我对着屏幕愣了好几分钟——为什么要移动那根矮的柱子这题适合两类人看一类是刚开始刷题、想搞明白双指针到底是怎么被“想出来”的人另一类是面试前想梳理高频题、并且准备好应对面试官连环追问的人。无论你是哪一类这篇文章都会把暴力解法、双指针原理、正确性证明、代码细节、常见坑和同类题一次性讲透。1. 题目还原先想清楚我们在算什么1.1 题面与示例原题描述非常短给你一个非负整数数组height每个元素代表一个垂直于 x 轴的柱子的高度下标代表柱子的位置。请你找出两个柱子使得它们与 x 轴共同构成的容器能容纳最多的水。换句话说任选两个下标i和ji j容器的底边长度是j - i容器的高度由两个柱子中较短的那根决定所以容积公式是min(height[i], height[j]) * (j - i)题目要你求这个式子的最大值。官方示例是height [1,8,6,2,5,4,8,3,7]答案是 49。这个 49 来自下标 1 的高度 8 和下标 8 的高度 7min(8,7) * (8-1) 7 * 7 49。很多新手上来会以为答案是下标 1 和下标 6 这两个 8 之间的组合min(8,8) * 5 40其实不是最大的。这个范例选得挺巧妙它能直接打掉“哪两根最高就选哪两根”的直觉。1.2 容易踩的直觉误区第一反应多半是暴力枚举这个没错但如果你以为这题只是“把所有组合算一遍”那你还没有摸到这道题真正想考的东西。它的数据范围是n 10^5暴力是 O(n^2)等数组长到几万在线评测系统直接给你超时。这题还有一个更隐蔽的误区有人会想能不能固定一个最高点然后左右扩展但容器高度受制于较矮的边最高点不一定能带来最大面积甚至面积最大的时候两根柱子可能都不是全局最高的。所以任何“只看高度”的策略在这里都会翻车。注意这道题本质上是在最大化一个由二元组决定的乘积而且乘积的两个因子——高度和宽度——存在拉扯关系宽度越大高度往往越小。你要找的是两者乘积最大的平衡点而不是单纯的高或者单纯的宽。2. 暴力解法先写出人人都会的版本2.1 暴力代码与思路暴力解法没什么技术含量就是两层循环枚举所有i j的组合逐个计算面积并更新最大值。def max_area_brute(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这段代码在数组长度只有几十的时候完全没问题逻辑也直白把所有可能的情况都看一遍答案必然在其中。2.2 复杂度与教训暴力做法的时间复杂度是 O(n^2)空间复杂度是 O(1)。当n 10^5时组合数接近 50 亿任何在线评测环境都跑不动。我最早刷这道题时第一版就交了暴力解法结果预期的超时提示如期而至。不过暴力解法的意义在于它提供了一个“基准答案生成器”。当你后面写出双指针解法时完全可以用小规模的随机数组把两种结果互相印证确认双指针版本没有算错。这个思路在刷题里很实用先用暴力解法当测试基准再优化能少走很多弯路。实操心得如果你在面试中一时想不出最优解先给暴力解法再把复杂度分析清楚然后自然过渡到更优方案面试官通常不会觉得你菜。最怕的是你暴力解法都不写干坐着憋大招。3. 双指针方案为什么移动矮的一边3.1 移动策略与直觉双指针解法的代码极短但它的核心只有一句话用两个指针分别指向数组的最左和最右每次计算当前面积并更新答案然后把高度较小的那根柱子对应的指针向中间移动一步重复直到两个指针相遇。用生活里最亲密的例子来理解想象你手里有一块木板左右各有一个支架木板能放多高的水取决于两个支架中较矮的那个。现在两个支架之间距离很大但有一只支架很矮水的高度被它压死了。你想让容积变大唯一可能的方向是换掉这只矮支架——因为如果你换掉高的那只新的支架只会更矮或持平而两个支架之间的距离还在缩小容积怎么可能变大呢所以每走一步我们都“放弃”当前较矮的柱子把赌注押在“另一侧可能存在更高的柱子”上。3.2 正确性证明这不是蒙对的是剪枝剪出来的有人会问你每次只移动矮指针凭什么保证丢掉的那一堆组合里没有最优解这就需要用反证法做一次严格的证明也是面试官最喜欢追问的点。假设最优解对应的两根柱子下标是(i, j)其中i j。算法从两端向中间逼近那么在某个时刻必然出现下面两种情况之一情况一左指针已经移动到i右指针还在j的右边设它是r即left i, right r j。如果此时height[i] height[r]那么当前左指针和右指针形成的容器面积min(height[i], height[r]) * (r - i) height[i] * (r - i)因为r j所以(r - i) (j - i)又因为min(height[i], height[j]) height[i]我们可以推出height[i] * (r - i) height[i] * (j - i) min(height[i], height[j]) * (j - i)右边正好是最优解的面积。这就说明在left i, right r的那一刻我们已经找到了一个比所谓“最优解”更大的面积产生了矛盾。所以不可能出现height[i] height[r]。于是必然有height[i] height[r]也就是说当前右指针是较矮的一边算法会移动右指针让它一步步向左靠近j从而最终走到最优解上。情况二右指针先到达j而左指针还在i的左边证明过程完全对称结论也一致。这个证明想说明的核心是在每一轮移动中我们丢掉的那些候选解要么已经被当前解覆盖要么严格劣于当前解。双指针之所以能用 O(n) 搞定是因为它用一次反证法把 O(n^2) 的组合搜索空间安全地剪掉了。注意这个证明有一个关键边界条件——如果两个指针高度相等移动哪边都可以。因为此时两边的“矮边”高度相同无论移动哪边都不会把更优的组合漏掉。但要小心代码里不能用if (h[left] h[right]) left; else right--;吗可以相等时默认移动右指针这也是安全的。3.3 高度相等的特殊处理当height[left]等于height[right]时很多实现都习惯把右指针往左移有些实现则喜欢左边右移、右边左移同时进行。其实移动单边就足够了因为容器的高度被这个相同的高度限制住宽度在缩小所以无论保留哪一边继续向内探索都不可能在这一步产生更大的面积接下来需要看的是中间区域有没有更高的柱子。移动单边的差异只影响遍历路径不影响最终答案。在实际代码里我推荐写成if height[left] height[right]: left 1 else: right - 1高度相等时走 else 分支右移一位逻辑简单也不容易写错。4. 代码实现与复杂度分析4.1 Python 版本def max_area(height): left, right 0, len(height) - 1 ans 0 while left right: h min(height[left], height[right]) ans max(ans, h * (right - left)) if height[left] height[right]: left 1 else: right - 1 return ans这段代码的核心就是 while 循环里的三步计算面积、更新答案、移动矮边。每次循环只做常数次操作循环最多执行n轮。4.2 Java 版本public int maxArea(int[] height) { int left 0, right height.length - 1; int ans 0; while (left right) { int h Math.min(height[left], height[right]); ans Math.max(ans, h * (right - left)); if (height[left] height[right]) { left; } else { right--; } } return ans; }Java 版和 Python 版在逻辑上完全等价。唯一的细节差异是数组长度为 0 或 1 时while 条件不成立直接返回 0这个行为恰好符合题意——只有一根柱子根本装不了水。4.3 复杂度与对比双指针版本的时间复杂度是 O(n)空间复杂度是 O(1)。解法时间复杂度空间复杂度适用范围暴力枚举O(n^2)O(1)n 1000仅用于验证双指针O(n)O(1)n 10^5面试标准解我实际跑过一组对比数据数组长度 10 万元素随机生成。暴力解法在本地环境跑到一半就被我手动终止了因为按每秒 10^8 次简单运算估算它需要 5000 秒以上。双指针版本在同一台机器上运行时间不到 1 毫秒。差距就是这么悬殊。实操心得写代码时先把 area 算出来再移动指针顺序反了会导致漏算初始状态的最大值。比如两个指针一开始就形成了最大面积结果你先移动了指针就把这个答案漏掉了。最稳妥的写法是先算、再比、最后移动。5. 常见错误与调试技巧5.1 四类高频错误这道题代码量小但错误率并不低。我见过最多的是下面这几种错误类型典型写法后果先移动再算面积循环开头先改指针漏掉初始状态或某些组合移动了高指针if (left right) left直接错过最优解while 条件多等号while (left right)两指针重叠时多算一次零面积影响不大但没必要宽度计算错误right - left 1容器宽度多算 1答案错误特别说一下宽度的问题。很多从“区间长度”习惯过来的人会写成right - left 1但这里的两根柱子只是立在数轴上中间的水域宽度等于下标之差而不是闭区间元素个数。比如下标 0 和下标 3容器底边长度是 3 而不是 4。这个细节很容易被忽略但一错就是整体答案全错。5.2 调试方法如果你发现答案不对最快的排查方式是在循环里打印每一步的状态while left right: h min(height[left], height[right]) area h * (right - left) print(fleft{left}, right{right}, h{h}, area{area}, ans{ans}) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1打印出来的每一行你都可以手动核验一次面积计算对不对指针移动的方向是不是指向矮边对比一下最终答案和暴力解法跑出来的结果。两个解法对拍是刷题验证正确性的最硬核手段。我建议所有人在初学阶段养成“用暴力结果验证最优解”的习惯遇到再复杂的题这个方法都能帮你快速定位逻辑错误。注意如果输入里有大数height[left] * (right - left)的结果在 C 里可能超过 int 范围建议声明为 long。虽然这题数据范围通常不会触发溢出但健壮性在面试中永远是加分项。6. 举一反三双指针的模式识别与同类题6.1 对撞双指针的适用条件这道题解出来不是终点“盛最多水的容器”只是双指针家族的一个代表。你需要从它身上抽象出一种可复用的思维模式当问题的答案由两个下标决定并且两个下标之间有某种单调的物理约束时就可以考虑从两端用对撞指针向内收缩。适合对撞双指针的题目通常有三个特征数据是数组或字符串答案与两个位置有关暴力遍历所有二元组是 O(n^2)需要降到 O(n)移动某一个指针时可以证明某些候选组合不会再成为最优解。如果你能清晰地说出“为什么排除这些候选”那你就真正掌握了对撞双指针而不是背了一套模板。6.2 同类题与差异点我知道很多人刷题喜欢按专题来那这里直接列几个和它高度相关的题目帮你把双指针的知识网络串起来。第一道是“接雨水”。同样是数组、同样是柱子、同样用双指针但接雨水需要对每个位置单独计算能存多少水而不是只找两个边界所以它的指针移动策略会更复杂维护的变量也更多。第二道是“三数之和”。它用到的思路是排序加双指针把三个数的问题降维成“固定一个数之后的两个数对撞”这个套路非常经典和盛水容器共享同一个“排序 对撞”的底层思维。第三道是“验证回文串”。它也是左右指针夹逼但它属于更简单的对撞场景——每次只比较两个字符不需要计算面积也不需要维护最大值。从这三道题回看盛最多水的容器你会发现它真正有价值的训练点有两个一是证明贪心策略的正确性二是把 O(n^2) 的枚举空间剪成 O(n) 的线性扫描。面试里能把这两点讲清楚的人远远比直接默写代码的人更让面试官印象深刻。我个人在实际刷题中还有一个体会第一次看这道题时卡住我的不是双指针这个名词而是“为什么可以放心地移动矮指针”。我后来把证明过程手写了三遍再遇到类似的对撞指针题思路就顺了。建议你也别急着背代码先花十分钟把第三节那个反证法推一遍这十分钟花得非常值。