“盛最多水的容器”这道题我前前后后刷了三遍每遍都有新收获。它几乎是所有算法面试题库里绕不开的一道题——输入一个整数数组每个元素代表一根竖立在x轴上的柱子的高度你要找到两根柱子让它们和x轴围成的容器能装最多的水。第一眼看上去这不就是两两组合算面积嘛暴力枚举不就行了但实际上它真正考的不是“你会不会算矩形面积”而是你能不能从 O(n²) 的暴力循环里跳出来用双指针在 O(n) 时间内解决问题。这篇文章我会从暴力解开始讲然后手把手推导双指针方案再给出可运行的代码和我在实际刷题中踩过的坑适合正在准备算法面试、或者刚开始接触双指针思想的读者。1. 先把题意吃透容器面积是怎么算出来的1.1 从数组到容器题面的几何化拆解题目给一个长度为 n 的整数数组 height下标从 0 开始。height[i] 表示在 x 轴坐标 i 处竖着一根高度为 height[i] 的柱子。你随便选两个下标 i 和 ji j两根柱子之间就形成了一条“底边”底边长度是 j - i而容器的高度由两根柱子中较矮的那根决定——这是木桶效应一个木桶能装多少水永远看最短那块木板。所以容器盛水的量在题目里被简化成一个二维面积area (j - i) * min(height[i], height[j])这里有两个点需要单独拎出来讲。一是为什么是“面积”而不是“体积”。这道题本质上是二维平面上求最大矩形面积的问题x 轴方向代表宽y 轴方向代表高相当于假设容器的第三维宽度为 1所以面积在数值上就等于水量。二是 min 这个操作是整个题目的命门。就算有一根柱子特别高比如 height[i] 9但旁边那根只有 height[j] 2那这个容器最多也只能装到 2 的高度水会从矮的那边溢出去。这个直觉极其重要后文推导双指针时核心逻辑全都围绕这个 min 展开。我补充一下数据规模。按照常见判题环境里的标准n 最少为 2最多可以到 10 的 5 次方每个 height[i] 的范围一般不超过 10 的 4 次方。这个数据规模直接决定了暴力解不可行具体账我们下一小节算。1.2 暴力枚举为什么不行复杂度账要算清最直接的解法两层 for 循环外层 i 从 0 跑到 n-2内层 j 从 i1 跑到 n-1枚举所有 (i, j) 组合每次计算面积并更新答案。def max_area_brutal(height): n len(height) ans 0 for i in range(n): for j in range(i 1, n): area (j - i) * min(height[i], height[j]) if area ans: ans area return ans这段代码没有任何逻辑错误在小数组上跑也是对的。问题出在组合数量上。当 n 10 的 5 次方时组合数是 n*(n-1)/2大约是 5 × 10 的 9 次方个。就算每次循环只做一次乘法和一次比较按一台普通开发机每秒能跑大约 10 的 8 到 9 次方次简单运算来算也要几十秒甚至几分钟才能跑完。在标准判题环境通常只有 1 到 2 秒时限的情况下这个解必然超时。顺便算一下空间复杂度暴力解只用了一个 ans 变量是 O(1) 的额外空间这点没问题。时间才是它的死穴。到这里你可能会想既然要遍历所有组合那就必须找到某种方式跳过大量无用的组合这就是双指针方案的出发点。下一节我们从头推导这个方案而不是直接背模板。2. 双指针方案的核心推导为什么移动短边2.1 从“两端夹逼”到状态空间剪枝双指针的思路一句话就能概括先把两个指针放在数组的两端此时底边最长是 j - i 最大的状态。然后每次移动“较短的那根柱子对应的指针”一步一步往中间收直到两个指针相遇。整个过程很像两个人从一排木板的左右两头往中间走每次都比一比谁矮谁矮谁就先让位。为什么一上来选两端因为在面积公式里宽度是一个重要因子。从最宽的位置开始我们只需要考虑“缩短宽度后高度能不能补回来”的问题而不用一开始就纠结哪两根柱子离得最近。你可以把整个搜索过程想象成我们手里有一个矩形初始时底边最长、高度由两端较矮的一端决定每移动一次底边变短一点但高度有可能变高面积也有可能变大。这套做法本质上是“状态空间剪枝”。所有可能的 (i, j) 组合本来是 O(n²) 个双指针每走一步就系统地排除掉一批不可能成为最优解的组合。关键问题是凭什么排除凭什么移动短边而不是长边这是整个算法最核心的一点我单独用一小节来讲。2.2 用反证式的推理证明指针移动规则假设当前状态是 left 和 right且 height[left] height[right]即左边是短边右边是长边。那么当前面积 S height[left] * (right - left)。现在考虑所有“左指针固定在 left右指针在 left 和 right 之间任意位置”的组合它们的宽度一定小于 right - left它们的高度由 min(height[left], height[任意位置]) 决定而不管右边界高度多大取 min 之后最多不会超过 height[left]。所以这些组合的面积全都 ≤ height[left] * (right - left) 当前面积 S。换句话说只要当前左边是短边那么所有“以 left 为左边界、右边界在它和 right 之间”的候选组合都不可能比当前状态更优可以整批丢掉。丢掉它们的唯一做法就是不把 right 往左移去枚举这些状态而是把 left 往右移让左边界换一个可能更高的柱子给高度一个提升的机会。对称地如果 height[right] 是短边那么所有“以 right 为右边界、左边界在 left 和 right 之间”的组合也都不会超过当前面积我们应该把 right 往左移。所以移动规则就一句话谁矮谁动。高的那根保持不动因为它还有可能在后续组合里成为“高边界”矮的那根已经没有利用价值了因为以它为短边的所有容器都被当前这个更宽的底“压住”了。这个证明还可以从“保持最优解”的角度理解。每一步我们都没有错过全局最优解当前所有未被排除的状态集合里至少包含一个最优解移动短边只是排除了确定不如当前的候选最优解要么是当前状态要么在剩下的状态里。这种“贪心移动 最优性保持”的结构是很多双指针题目的共性。2.3 完整手动模拟一遍用经典示例走查光讲理论还是有点抽象我拿一个非常经典的用例手动走一遍height [1, 8, 6, 2, 5, 4, 8, 3, 7]。这个数组在很多讲解里都会出现因为它刚好能体现双指针的每一步选择。初始 left 0高度 1right 8高度 7短边是左边当前面积 (8-0) * min(1, 7) 8答案暂记为 8。根据规则移动短边left 变成 1。left 1高度 8right 8高度 7短边在右边面积 7 * 7 49答案更新为 49。移动短边right 变成 7。left 1高度 8right 7高度 3面积 6 * 3 18不更新。移动短边 rightright 变成 6。left 1高度 8right 6高度 8两边相等面积 5 * 8 40不更新。等号时移动哪边都行按常见写法移动右指针right 变成 5。left 1高度 8right 5高度 4面积 4 * 4 16不更新。移动右边right 变成 4。left 1高度 8right 4高度 5面积 3 * 5 15不更新。移动右边right 变成 3。left 1高度 8right 3高度 2面积 2 * 2 4不更新。移动右边right 变成 2。left 1高度 8right 2高度 6面积 1 * 6 6不更新。此时左右指针相邻再移动任意一个就会相遇循环结束。最终答案是 49对应下标 1 和下标 8 这两根柱子。这个例子有个特别好的地方最优解的两个端点一开始并不是最宽的但双指针通过不断排除不可能的区间找到了它。建议你在纸上多推两个不同的用例比如所有高度都递增、所有高度都相同、只有一个高峰的情况推完再去看代码会顺畅非常多。3. 代码落地三种主流语言的实现与细节3.1 Python / C / Java 双指针模板Python 版本from typing import List class Solution: def maxArea(self, height: List[int]) - int: left, right 0, len(height) - 1 ans 0 while left right: area (right - left) * min(height[left], height[right]) if area ans: 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 (int)height.size() - 1; int ans 0; while (left right) { int area (right - left) * min(height[left], height[right]); if (area ans) ans area; if (height[left] height[right]) { left; } else { --right; } } return ans; } };Java 版本class Solution { public int maxArea(int[] height) { int left 0, right height.length - 1; int ans 0; while (left right) { int area (right - left) * Math.min(height[left], height[right]); if (area ans) ans area; if (height[left] height[right]) { left; } else { right--; } } return ans; } }三份代码的核心逻辑完全一致。while 循环的条件是 left right当两个指针相遇时宽度变成 0继续算面积没有意义所以循环必须在这里终止。每次迭代的顺序是固定的先算面积、更新答案再按短边规则移动指针。顺序不能反否则你会漏掉当前状态或者多算一个已经不该考虑的无效状态。有一点要说清楚height[left] height[right] 时我写的 else 分支会把右指针往左移。其实移动左边也完全可以因为两边等高时不管移动哪边丢掉的都是“不可能更优”的那一批组合。你可以从 2.2 的推理里推出来两边相等时短边是左右两边中任意一边所以两边都可以作为被移动的那根。为了代码简洁写成 else 统一处理即可。3.2 容易被忽视的边界与溢出细节细节一n 2 的处理。按题目要求 n 最少为 2通常不用特判。但如果把这个函数封装成公共工具给别人用最好加一句 if (len(height) 2) return 0防止有人传一个空数组或者单元素数组。细节二容器面积是否会溢出。在常见的约束下n 最大 10 的 5 次方height 最大 10 的 4 次方最大面积大约是 10 的 9 次方32 位 int 的上限是 2.147 × 10 的 9 次方理论上不会溢出。但如果数据范围加大或者你在本地处理更大规模的数据建议直接用 long longC或 int64答案和中间乘积都用 64 位省得排查半天发现是溢出问题。细节三min 的调用次数。每次循环只调一次 min整体 O(n) 次完全没问题。有些追求极致性能的写法会用条件判断替代 min例如 int area (right - left) * (height[left] height[right] ? height[left] : height[right])本质上一样看个人代码风格。细节四指针移动时务必保证 left right 的约束。这个约束由 while 条件天然保证但如果你在循环体里连续移动两次指针比如某些错误写法里“为了处理相等情况同时移动两边”就可能出现 left 越过 right 的情况一定要避免。我的建议是一次迭代只移动一个指针代码最好懂也最不容易出错。4. 实战踩坑记录这些错误我全犯过4.1 误区一贪心地去移动那根更长的柱子我第一次做这道题的时候脑子里没有“短边决定容量”这个意识想当然地觉得底边越长面积越大所以应该尽量保持宽度移动高的那根。结果每次移动的都是长边碰到 [1, 8, 6, 2, 5, 4, 8, 3, 7] 这种例子根本得不出 49因为右边那根高度 7 的柱子被过早移掉之后再也没有能和左边高度 8 组成大容器的高边界了。后来我才意识到问题的关键不是“底边长度”而是“面积由短边决定”。你保留长边实际上保留的是一个未来可能提供更高高度的机会你移动短边是因为以它作为短边的所有状态已经被当前状态压住了。这个直觉一旦建立写代码就是水到渠成的事。4.2 误区二面积计算的时机与状态更新顺序另一个常见错误是把更新答案和移动指针的顺序写反。比如下面这种写法while left right: if height[left] height[right]: left 1 else: right - 1 area (right - left) * min(height[left], height[right]) ans max(ans, area)这种写法每次先移动指针再算面积完全漏掉了初始最宽状态。极端情况下如果最优解恰好是首尾两根柱子组成的容器答案里永远不会有它。正确顺序应该如 3.1 的模板所示先基于当前两个指针位置计算面积再更新答案最后移动指针。4.3 误区三高度相等时不知道该动哪边不少初学者在 height[left] height[right] 时会纠结担心移动哪边会丢掉最优解。实际上两边相等时两个方向的剪枝性质是对称的移动任何一边都不会丢解。比如用一组全部相等的数组验证[3, 3, 3, 3, 3]最大宽度是 4min 高度是 3最大面积一定是 12。无论你每次只动左边、只动右边还是交替动最终答案都会落到 12。这个结论我建议你自己写代码验证一次心里会比较踏实。4.4 怎么给自己写一套可靠的验证方法面试的时候你没法临时造数据但在本地练习时可以做得更严谨。我最常用的方法是写一个随机测试脚本随机生成一个长度不超过 200、高度不超过 20 的数组先用暴力枚举算出一个标准答案再用双指针算一次两者对比。如果一致就继续如果不一致就把数组打印出来手动模拟定位问题。import random def brute(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 two_pointer(height): left, right 0, len(height) - 1 ans 0 while left right: ans max(ans, (right - left) * min(height[left], height[right])) if height[left] height[right]: left 1 else: right - 1 return ans for _ in range(1000): h [random.randint(0, 20) for _ in range(random.randint(2, 200))] if brute(h) ! two_pointer(h): print(mismatch, h) break else: print(all ok)这个脚本一分钟内能跑几千组随机数据比手动构造用例高效得多。你可能会说这么简单的题还需要随机验证吗其实越简单的题越值得这种验证因为人的直觉容易在某些边界状态下失效而随机测试能快速暴露问题。5. 跳出这道题双指针思维能解决的一大类问题5.1 沾亲带故的题目三数之和、接雨水、回文串判定“盛最多水的容器”不是孤立的一道题它属于一大类“左右双指针”问题。我把代表性题目放在一起对比一下题目类型双指针前提核心剪枝依据盛最多水的容器无需排序短边限制容器高度上限两数之和有序数组数组有序和与目标值之间的单调关系三数之和先排序固定一个数后区间内单调夹逼接雨水需要预处理左右最高点偏低侧的柱子无法存储更多水回文串判定无需排序两端字符相等才能继续向内其中接雨水的解法和本题不完全相同但核心直觉相通水的容量受较矮一侧的峰值限制。回文串判定是最简单的双指针应用两个指针从字符串两端向中间走一旦发现字符不相等就返回 false。对比这些题目你会发现一个共性当两个指针从两端向中间推进时每一步都能根据当前状态的信息确定性地丢弃一部分不可能成为答案的状态从而把 O(n²) 降到 O(n)。5.2 双指针思维模型的本质与迁移方法要说清楚这个思维的本质我想用一个类比假设你站在一排高低不同的木板前想找两块木板围一个最大的水桶。从最外侧开始如果左边比右边矮那么这块矮木板和右边任意一块木板组合都不可能装得比现在更多——因为水位都被这块矮板限制住了而且距离还在缩短。所以这块矮板可以放心地丢弃接下来去下一块更高的板上碰碰运气。迁移到别的题目核心动作就是三步。第一步找到两个端点明确当前状态给出的信息比如面积、和、差值等。第二步基于某种单调性判断哪一侧的状态是可以被整批排除的。第三步移动对应的指针进入新状态重复上述过程。你不需要把每一道双指针题都单独背下来只要判断出状态空间里存在一个方向上的单调性使得我们可以安全剪枝就大概率能用双指针。这也是为什么这类题目值得反复刷的核心原因。我个人真实的体会是这道题的价值不在那几十行代码而在于它逼你回答一个“为什么”。暴力解谁都会写双指针的代码也不难背但如果你能亲手推导一遍“为什么移动短边为什么可以整批丢弃状态”你对双指针这类算法的理解就会上一个台阶。后面我再去刷接雨水、三数之和这些题明显顺畅了很多。如果你刚开始刷算法题建议把这道题当成双指针的入门必修课多推几遍、多错几次比单纯背模板有价值得多。