刷LeetCode和准备Java面试的人大概率都会碰到这道“盛水最多的容器”。它经常和“接雨水”“三数之和”摆在一起被当作双指针法的入门代表题。很多人第一次看题会想不就是找两条线围出来的最大面积吗直接双重循环把所有组合都算一遍不就行了但等你真把代码提交上去就会发现数据量一大直接超时面试官也会皱眉头。这道题真正想考的不是“你会不会暴力枚举”而是你能不能想到用双指针把 O(n²) 暴力优化成 O(n) 的线性扫描并且能讲清楚为什么移动指针的时候不会错过正确答案。这篇文章我会把这题从读题、推导、写代码到踩坑复盘完整走一遍。不光是给你贴一段能跑的Java代码更会展开讲“为什么要移动矮的那一侧指针”“为什么双指针不会漏掉最优解”“相等高度到底怎么处理”最后再延伸一下双指针家族里其他几道常考题方便你在面试时把相关知识串起来。我默认你是Java基础已经过关、正准备刷算法题或者突击面试的开发者。如果你还在学循环、数组这些基础语法这篇文章也能看懂因为代码部分很短难点全在思路推导上我会尽量用大白话把推导过程讲清楚。1. 题目复盘与双指针思路的由来1.1 题目到底在问什么先还原一下题目本身的表述。给定 n 个非负整数 height[0]、height[1]……height[n-1]每个整数代表坐标轴上某个点的高度从 (i, 0) 到 (i, height[i]) 画一条垂直线。现在要从中选两条线和 x 轴一起组成一个“容器”问这个容器最多能装多少水。这里有个很容易忽略的点装水量不是简单的两条线高度之和乘以距离而是两条线中较短的那条高度乘以两条线的水平距离。换句话说水会从矮的那一侧溢出来高的一侧再高也没用容器的高度被短板牢牢限制住。用公式表达就是容量 min(height[l], height[r]) × (r - l)其中 l 和 r 分别是两条线的下标r - l 是它们之间的水平距离。理解了这个公式后面所有优化思路都从它出发。举个例子height [1,8,6,2,5,4,8,3,7]最优解是选下标 1 高度 8 的那条线和下标 8 高度 7 的那条线min(8,7) × (8-1) 49。这个 49 就是经典答案。如果你把两条线都选得很高但距离太近面积反而小距离拉得远但如果其中一条很矮面积也大不到哪去这就是题目有意思的地方容量由“距离”和“短板”共同决定最优解往往需要在这两者之间找平衡。1.2 暴力解法为什么连及格分都拿不到拿到题第一反应肯定是暴力枚举外层循环固定左边界内层循环遍历右边界把所有 (i, j) 组合的面积都算一遍更新最大值。代码确实简单两层 for 循环加一个 Math.min 就算完了。问题出在时间复杂度上。假设数组长度是 n所有配对的数量是 n × (n-1) / 2也就是 O(n²) 量级。如果 n 是几千还好说但 LeetCode 这种在线评测系统通常会把数据范围拉到 10⁵ 甚至 10⁶O(n²) 意味着要执行上亿次循环最终结果只有一个超时。面试场景里更致命的是哪怕你不写代码只说“我用两层循环把所有情况都算一遍”面试官基本也能判断你对这道题的理解停留在什么层面。因为这道题存在的意义就是要打破“所有组合都要检查”的思维惯性——很多组合是注定不可能成为全局最优解的根本不需要算。你能找出这些“注定不可能”的组合并跳过它们才是本题真正的考点。所以暴力解法适合用来验证思路和写测试用例但不适合作为最终答案。2. 为什么双指针一定不会漏掉最优解2.1 移动短板才有机会变大双指针方案的起点很朴素先用最左边和最右边两条线作为初始容器因为这时的水平距离是最大的。然后让指针逐步往中间靠拢每次只移动一个指针同时更新最大面积。关键问题来了两个指针每次到底移动哪一个直觉上有人会说“把高的留下移动矮的”也有人会想“把矮的留下移动高的因为移动高的一侧距离变小但高度还能保持”。到底哪个对我们用公式推一下。假设当前左指针 l 指向的高度是 h_l右指针 r 指向的高度是 h_r并且 h_l h_r。当前的容量是 h_l × (r - l)。如果此时移动右指针也就是比较高的那一侧让它向左挪一步新的距离变成 r - l - 1新的高度是 min(h_l, height[r-1])。由于 h_l 本来就矮新的 min 值最多也就是 h_l不可能超过它所以新容量最多是 h_l × (r - l - 1)比当前容量严格更小。换句话说移动高的那一侧无论右边新的高度是更高还是更矮容器容量都不可能变大因为“矮的那条线的上限”没变距离反而缩短了。那移动矮的那一侧呢虽然距离同样缩短了但新的高度可能比原来那条矮线更高只要高度的提升能弥补距离的缩短容量就有机会变大。所以正确策略只有一个每次比较左右指针的高度移动较矮的那一侧。我常用一个生活化类比帮助记忆两个人合作抬水桶能装多少水永远取决于个子矮的那个人。矮个子往中间走一步换一个更高的矮个子来桶的容量才有可能提升高个子往里走整体高度还是受矮个子限制只会白白把距离缩短。2.2 区间收缩与最优解保留有人会担心每次都只检查一个组合会不会漏掉某些没检查过的组合但那些恰恰才是最优解这个担心很合理毕竟暴力解法之所以“暴力”就是因为它不信任任何跳过逻辑。双指针的信任基础是一个很朴素的剪枝逻辑每一步移动之前当前指向的这对边界组合已经被“检查完毕”了它不会成为最优解但它所代表的“可能性边界”需要被收缩。当我们移动较矮的那一侧指针时本质上是排除了“当前矮边界与区间内任意其他右侧线组成容器”的所有可能性。为什么能排除因为当前矮边界的高度是 h其他任意右侧线距离当前右边界都更近距离最大也只有 r - l - 1高度最多也就是当前矮边界相对的另一侧线可能更高但由于有当前矮边界 h 参与任何包含当前矮边界的容器高度都不可能超过 h所以这些组合的容量全部小于等于 h × (r - l - 1)不可能打败一个已经存在的、基于更宽距离算出来的至少为 h × (r - l) 的候选值。因此把矮边界扔掉是完全安全的。随着指针不断向中间收拢搜索区间持续缩水但每一步缩水都只剔除“必败组合”最优解如果存在于被剔除的那一侧等于它被更高分选手淘汰了不影响最终答案。等左右指针相遇所有可能成为最优解的组合都已经检查完毕maxArea 就是全局最优。这个证明思路面试时常考你不需要背原话但要把“移动高指针高度不会增加、距离反而缩短所以永远移动矮指针”的推导写在草稿纸上。2.3 高度相等时的处理细节当左右指针指向的高度相等时比如 height[l] height[r]移动哪边其实都不影响最终答案。原因很简单当前组合已经被检查过了而无论移动左边还是右边新的容量都要在距离减 1 的基础上重新计算两边机会均等。但代码实现时大多数人会写成 if (height[l] height[r]) l; else r--;这样做唯一的小问题是当两者相等时会移动右指针。也可以写成 把相等情况归到左边移动。两种写法结果完全一致。真正要避免的是在相等时同时移动两个指针也就是写 if (height[l] height[r]) { l; r--; }这等于是跳过了中间一些可能的组合比如左边移动一步后的新高度很高、右边只移动一步后的新宽度还很大这种组合可能成为更优解但直接被跳过了。一次循环只移动一个指针是双指针法的通用纪律能保证搜索路径覆盖完整。3. Java代码实现与易错点3.1 十几行代码写干净整体代码其实很短核心就一个 while 循环。我习惯先把边界条件处理掉再做双指针扫描。public int maxArea(int[] height) { if (height null || height.length 2) { return 0; } int left 0; int right height.length - 1; int maxArea 0; while (left right) { int minHeight Math.min(height[left], height[right]); int currentArea minHeight * (right - left); maxArea Math.max(maxArea, currentArea); // 移动较矮的一侧高的一侧不动 if (height[left] height[right]) { left; } else { right--; } } return maxArea; }这段代码有几个地方值得展开讲。先把 Math.min 的结果单独存成 minHeight再用它计算面积这样比每次写 height[left] height[right] ? height[left] : height[right] 清晰得多也方便调试时打印变量。其次 maxArea 的初始值是 0因为任何有效容器的面积都是非负数0 作为初值不会污染结果。最后是 while 条件用 left right如果写成 left right当左右指针相遇时 right - left 等于 0面积永远是 0虽然不会报错但多算一步无意义操作风格上不推荐。3.2 容易被问到的两个细节第一个细节是 int 溢出。height 数组里每个元素通常是非负整数假设元素最大是 10⁴数组长度最大是 10⁵那最大面积大概是 10⁴ × 10⁵ 10⁹int 的极限是 21亿多所以原题范围内 int 完全够用。但如果你在面试时被追问“如果把 height 的元素范围放大到 10⁹ 呢”就要说清楚这时候应该用 long 计算乘积或者把方法返回值改成 long。我个人的习惯是在注释里标注一下这个假设避免后续维护者误用。第二个细节是左右指针移动时要不要做“高度优化跳跃”。网上有些写法会写成 while (left right height[left] minHeight) left;意思是跳过所有比当前矮边界还矮的线因为它们的容量肯定更小。这个优化本身是对的在数据特别极端时能省掉一些无效计算但对这道题来说反而容易引入 bug如果跳过得太狠可能把中间一个较高但距离已经变短的组合漏掉还要额外处理数组下标越界问题。对一道讲求稳定性的面试题一次移动一步是更稳妥的选择。真想优化等代码跑通后再考虑加跳跃逻辑并且一定要配合完整测试用例验证。4. 常见错误与调试实录4.1 踩过的坑边界条件和指针移动写反写这种题的经典翻车场景我列一下每一条都是我实际见过或者自己踩过的第一while 条件写成 left right。这会导致左右指针相遇后继续执行此时 right - left 是负数乘出来的面积变成负数虽然 maxArea 不会因此变小但在某些变形题里会造成数组越界访问。正确写法是 left right因为当两个指针重叠时它们代表同一条线围不成容器。第二计算面积时用了 height[left] 和 height[right] 的较大值而不是较小值。有人会写 int area Math.max(height[left], height[right]) * (right - left)然后发现怎么也得不到正确答案。这是把“水从高的一侧溢出”这个物理事实给忘了容器高度永远是短板不是长板。第三指针移动方向和高度比较搞反比如 if (height[left] height[right]) right--;。这样会把高的一侧往里收矮的一侧留在原地循环跑完某些测试用例会得到偏小的结果。调试时会发现每次移动到后期左边始终是一个特别矮的线面积一直被它压着。第四数组为空时没做保护。如果输入是空数组或者只有一条线left 和 right 的初始值会让 Math.min 直接报错。所以 maxArea 方法开头必须处理 height null 或 height.length 2 的情况。我把这些问题整理成一张速查表方便你自查症状原因修复数组越界异常while 条件写成 left right相遇后继续访问改成 left right输出面积偏小用 Math.max 而非 Math.min 计算容器高度改成 min(height[l], height[r])输出全是 0移动指针时移动了高的一侧换成 height[l] height[r] ? l : r--空数组报错缺少边界条件开头加 null 和 length2 判断死循环相等高度时同时移动两个指针或没移动指针一次只移动一个指针且保证有移动4.2 性能与正确性验证代码写完不能直接提交最少要用两组数据验证。第一组是题目自带的示例height [1,8,6,2,5,4,8,3,7]期望结果是 49。我建议你像写单元测试一样自己跑一遍并在循环内部打印 left、right、minHeight、currentArea 几个变量确认每一步的面积变化是否符合预期。第二组是边界数据比如 height [1, 1]两条等高线距离为 1面积是 1height [1, 2, 1]面积是 min(1,1) × 2 2height [1] 和 height [] 都应该返回 0。这些边界数据看似简单但最容易暴露数组越界和初值错误。性能层面暴力法在数据量到 10⁵ 时运行时间通常是几十秒甚至更长而双指针法的时间复杂度是 O(n)空间复杂度是 O(1)只需要两个指针变量和一个最大值变量。我实测过 n 10⁶ 的随机数组双指针版本在普通笔记本上也就几毫秒完成差距非常明显。这也是为什么面试官特别偏爱这题它能一次性考察你的复杂度分析能力、双指针理解和代码稳定性。5. 从这道题看双指针家族与面试加分项5.1 同门师兄弟接雨水、三数之和、最长回文子串盛水最多的容器是双指针思想的入门题但双指针本身是一整个家族刷题时建议把下面几道连在一起练因为它们的核心套路相通接雨水LeetCode 42是这道题的升级版。它不再是选两条线算一个容器而是计算整个数组中所有凹槽能接住的总水量。思路依然是用左右指针从两端往中间走同时维护左右两侧遇到的最大高度 leftMax 和 rightMax哪边最大值更小就移动哪边的指针并按 min(leftMax, rightMax) - height[current] 累加水量。你会发现它的移动策略和盛水容器几乎是同一个逻辑矮的一侧有优先权。三数之和LeetCode 15则是双指针的另一个经典用法。先把数组排序固定一个数作为第一个加数然后在剩余区间里用两个指针从两端向中间扫描根据三数之和与目标值的大小决定移动左指针还是右指针。排序是这里的关键前提没有排序就没法判断该往哪个方向移动。最长回文子串可以用中心扩展法虽然结构上不那么像双指针但本质也是从某个中心点向两侧同时扩散每次扩散都检查左右字符是否相等。还有移除元素的原地操作、链表判环的快慢指针都属于双指针思想的不同变体。把这些题串在一起你对“双指针的本质是在有序或可推导的方向上用两个游标缩小搜索空间”这句话会理解得更深。5.2 面试时这样答才加分如果面试官让你现场做这道题我建议按这个顺序回答这个方法能很好地体现你的思维层次第一步先说暴力思路明确给出复杂度是 O(n²)、O(1)让面试官知道你理解问题的朴素解法是什么。第二步指出暴力枚举有很多组合“必输”因为容器高度受短板限制距离一定缩短时容量不可能超过当前候选值。第三步提出用左右指针从两端开始扫描每次移动较矮的指针同时维护 maxArea最终复杂度降到 O(n)。第四步现场写代码重点展示你对边界条件的处理和对 Math.min 的理解。很多同学卡在第二步讲不清楚为什么能跳过那些组合。你只要把“移动高指针min 值不会变大距离一定变小面积必然变小”这句话说出来面试官基本就会点头。这比把代码背得滚瓜烂熟更管用因为他能确认你是真的懂原理而不是刷题背答案。我个人在实际刷题中的体会是这道题值得你合上题解自己从头推导一遍双指针的移动策略。我第一次做的时候也困惑了很久总觉得可能漏掉某些组合后来在草稿纸上画了几组高度分布图把每次移动后被排除的区间写出来才真正信服“矮指针可以安全移动”这件事。从那以后凡是遇到左右指针类的题目我第一反应都是先问自己一句这一步移动哪个指针以及为什么移动它是安全的。如果你能把这种思维习惯带到后面的题目里刷题效率会提升很多。最后再分享一个写这类题的小技巧代码里不要省略中间变量哪怕只为了让当前面积更直观。你可以把 if 分支里移动左指针和移动右指针的逻辑写得对称一点这样后续想加日志、加断言、做单元测试都会方便很多。算法题的代码虽然短但它是你思路的投影写得清爽的人思路通常也是清爽的。