到O(n))
刷LeetCode的人迟早会和《盛最多水的容器》打个照面。这道题编号是第11题，看起来很直观，实际上考的是你对“搜索空间压缩”的理解：一个数组里任意两个位置围出来的矩形面积，怎么在最短时间内找到最大。我第一次做这题时，第一反应就是两层循环把所有组合算一遍，觉得这不就完事了；后来看到双指针解法，恍然大悟，但真让自己把“为什么移动短边不会漏掉答案”讲清楚，还是卡了壳。这篇文章就把这题的数学模型、双指针原理、代码实现、常见坑和面试表达一起拆开讲，适合刚准备算法面试的人，也适合已经刷过一遍但还想加深理解的人。
1. 题目到底在问什么：把“盛水”翻译成数学模型
1.1 从题目描述到数组坐标
题目会给你一个整数数组height，数组的长度表示有这么多条竖线，下标i是横坐标，height[i]是这条竖线的高度。你要在这个二维坐标系里选两条竖线，和 x 轴一起组成一个“容器”，容器能装多少水，取决于两块板里较短的那块板的高度，再乘以两块板之间的水平距离。
数学表达式就是：
面积 = min(height[i], height[j]) * (j - i)注意下标j > i。这就是水桶效应在算法题里的呈现：能装多少水，不由最长的那块板决定，而由最短的那块板决定。这个公式如果你自己在纸上画几个矩形，会特别有体感。
官方示例里那个数组是[1,8,6,2,5,4,8,3,7]，答案是 49。为什么是 49？因为下标 1 和下标 8 对应的高度分别是 8 和 7，距离是 7，短边是 7，面积就是7 * 7 = 49。这个例子后面可以用来验证代码。
这里我建议先别急着看答案，而是拿出纸笔画一个数组，把每根竖线画出来。你会发现这题虽然叫“盛水”，但本质就是个几何面积最大问题，和你想的“容器是不是封闭”“水会不会漏”完全没关系。题目看重的是数学抽象能力。
1.2 先看最朴素的双层循环思路
对于刚接触算法题的人来说，最容易想到的就是枚举所有可能的两根竖线组合。两层 for 循环，外层枚举左指针i，内层枚举右指针j，每次计算面积，不断更新最大值。
用伪代码写就是：
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这段代码本身没什么错误，结果一定是对的。问题出在复杂度：组合数量是n * (n - 1) / 2，也就是 O(n²)。LeetCode 的约束通常把数组长度拉到 10 的 5 次方级别，O(n²) 要算 10 的 10 次方次，现代机器也很难在限定时间内跑完。
暴力解法虽然超时，但它在面试里其实有它的价值。你可以先说出这个最自然的思路，让面试官知道你能理解问题；然后再提出优化方案，展示你具备从坏方案走向好方案的能力。最怕的是上来就默写双指针，但又说不清楚为什么，这在面试中反而会暴露理解深度不够。
1.3 直觉是怎么来的：从最宽处开始收缩
为什么双指针能在 O(n) 时间内解决问题？核心直觉是这样：先把两根指针放在数组最左和最右，这时候宽度最大，面积是min(height[left], height[right]) * (n - 1)。接下来如果想把面积变大，宽度只会越来越小，所以必须让“短边的高度”尽量提高。
假设height[left] < height[right]，也就是短板在左边。现在你面临两个选择：移动左指针，还是移动右指针？如果移动右指针，那么新的右指针不管多高，容器的高度仍然被左边的短板限制，甚至可能更矮；同时宽度还变小了，所以面积不可能变大。反过来，移动左指针，还有机会遇到更高的左边竖线，从而突破刚才那个高度瓶颈。
这个思路不需要严谨证明，也能让人快速接受。双指针解法不是凭空冒出来的，它来自对面积公式“宽度在减少，高度只能看短边”的观察。先把这层直觉建立起来，后续看证明会舒服很多。
2. 双指针核心原理与正确性证明
2.1 指针移动规则与代码骨架
双指针的做法很固定，先贴一个核心骨架：
left = 0 right = n - 1 ans = 0 while left < right: area = min(height[left], height[right]) * (right - left) ans = max(ans, area) if height[left] < height[right]: left += 1 else: right -= 1每次循环只做两件事：计算当前两根指针形成的面积，然后移动高度较小的那一根指针。如果两边高度相等，移动哪边都可以，不会影响最终答案。
这个代码骨架第一次看会觉得很神奇：明明有 O(n²) 种组合，为什么只移动指针就能找到最优解？其实关键在于每一次移动，都“剪掉”了一整批不可能成为答案的候选组合，而不是只排除了当前这一种组合。理解这一点，才算真正懂了双指针。
2.2 为什么移动“较短边”一定安全：一个不等式证明
这里我还是想用数学方式把“移动短边不漏答案”这件事讲透。假设当前左指针是i，右指针是j，并且height[i] <= height[j]，也就是左边是短边。
当前面积是：
min(height[i], height[j]) * (j - i) = height[i] * (j - i)现在如果保持i不动，让右指针向左移动到任意位置k，其中i < k < j，那么新面积是：
min(height[i], height[k]) * (k - i)因为不管height[k]是多少，min(height[i], height[k])一定小于等于height[i]；同时k - i < j - i。所以这个新面积一定严格小于当前面积。换句话说，在当前这一轮里，任何“以i为左边界，右指针往左挪”的候选组合，都不可能超过当前这个面积。
因此，我们可以放心地把左指针向右移一位，丢掉所有以i为左边界但还没被检查过的组合，因为它们已经被证明不会成为全局最优。另一边高度相等时也一样，min的结果都被短板限制，宽度又在减少，所以移动任意一边都可以。
这个证明的实质就是：双指针不是用暴力遍历所有状态，而是利用“面积公式具有单调限制”这一性质，成片地排除无效状态。能在面试中说出这一步，基本就比只会背代码的人高出一个段位。
2.3 复杂度分析：从 O(n²) 到 O(n) 的搜索空间压缩
双指针整个过程里，left只能向右移动，right只能向左移动，两个指针一共移动n - 1次就会相遇，所以只计算了n - 1种候选状态。每次计算面积和比较更新都是 O(1)，时间复杂度就是 O(n)，额外空间只有两个整数，空间复杂度 O(1)。
这里有人会问：只检查n - 1种状态，凭什么不漏答案？答案就在上一节的证明里：每移动一次指针，我们就排除了一个“不可能成为最优解”的区间集合。相当于把 O(n²) 的搜索空间按规则剪枝，剪到最后只需要看一条路径上的状态，而全局最优就藏在这条路径上。
这种搜索空间压缩的思想，比这道题本身重要得多。以后你会遇到很多看似需要枚举的题，其实都可以用“单调性剪枝”来优化。遇到这类题，先想想能不能让两个指针按某种方向单调移动，往往就离正确解法不远了。
3. 代码实现与调试细节
3.1 Python 和 C++ 版本
Python 版本写起来非常简洁：
def maxArea(height): left, right = 0, len(height) - 1 ans = 0 while left < right: area = min(height[left], height[right]) * (right - left) ans = max(ans, area) if height[left] < height[right]: left += 1 else: right -= 1 return ansC++ 版本要注意下标类型和vector的访问：
class Solution { public: int maxArea(vector<int>& height) { int left = 0, right = height.size() - 1; int ans = 0; while (left < right) { int h = min(height[left], height[right]); int w = right - left; ans = max(ans, h * w); if (height[left] < height[right]) { ++left; } else { --right; } } return ans; } };两个版本的逻辑完全一致。我建议初学者在本地编辑器里把输入输出部分补全，随便造几个数组跑一跑，加深印象。直接在网页上提交虽然也能学，但手动调试一遍，收获会大很多。
3.2 几个容易写错的细节
第一个细节：宽度是right - left，不是right - left + 1。两根竖线的宽度等于它们下标的差值。比如左边在下标 1，右边在下标 8，中间隔了 6 个位置，宽度就是 7。很多人受“数组长度 = 下标差加一”的影响，这里容易多算 1。
第二个细节：先算面积，再移动指针。顺序如果反了，当前状态就会被跳过。虽然最终答案可能不受影响，因为如果当前状态不是最优，跳过也没关系；但这不是你写程序应该依赖的运气。逻辑正确、步骤清晰，才便于排查问题。
第三个细节：两边高度相等时，不要想着“两边一起移”。同时移动两边可能会漏掉最优解。比如某个最优组合恰好用到了当前的两块等高木板中的一块，你一手一个同时跳过，就把这条候选路径丢掉了。虽然前面证明过移动任意一边都安全，但“两边都移”并不在安全证明范围内，别自作聪明。
第四个细节：在 C++ 里，如果height.size()返回的是size_t，你可能需要留意无符号类型和int混用的问题。LeetCode 的数组长度不会大到离谱，但更好的习惯是直接使用int left = 0, right = (int)height.size() - 1;，避免后续比较出现类型警告。
3.3 手动跑一个例子：验证你的代码
我来手动模拟[1,8,6,2,5,4,8,3,7]的开头几步，方便你对照。
初始left=0, right=8，高度是 1 和 7，面积是min(1,7)*8 = 8，更新ans=8。因为height[0] < height[8]，移动左指针到 1。
接着left=1, right=8，高度是 8 和 7，面积是min(8,7)*7 = 49，更新ans=49。此时height[1] > height[8]，移动右指针到 7。
再下一步left=1, right=7，高度是 8 和 3，面积是min(8,3)*6 = 18，小于 49，不更新。height[1] > height[7]，移动右指针到 6。
之后left=1, right=6，高度是 8 和 8，面积是min(8,8)*5 = 40，还是小于 49。两边相等，按代码会移动右指针到 5。后面继续走到结束，最后答案就是 49。
建议你也自己把整个过程推完，不要只停在这几步。手动推演会让“指针为什么往这边走”变得非常有画面感，比看十遍题解都管用。
4. 常见问题与排查技巧
4.1 为什么我的双指针结果不对
常见的问题无非这几种：结果偏大、结果偏小、死循环。
结果偏大，大概率是宽度算错了，用成了right - left + 1，把边界上的距离虚拟地多加了一单位。结果偏小，可能是更新ans的时机不对，或者把移动指针写在了计算面积之前。死循环则多半是while里的left < right条件写成了left <= right，或者指针移动语句被忘在了条件分支外面。
排查这些问题的办法非常朴素：在循环里打印left、right、area、ans四个值。一旦出现某个面积骤减但指针没有按预期移动，你立刻就能看到原因。算法题排错不一定要靠调试器，最简单的日志输出往往最有效。
还有一种隐蔽错误：比较高度时用了<=，两边相等时移动左指针；下一次循环里，如果两边还是相等，又移动左指针。这其实是安全的，不会漏解。真正的不安全操作是同时移动两边指针，这点前面强调过，建议在写代码时用注释明确标记一下“只移一边”。
4.2 这题和“接雨水”到底有什么区别
很多人刷题时会把《盛最多水的容器》和《接雨水》放在一起做，然后越做越混。其实它们的计算目标完全不同：这题是让你在数组里选两条竖线，围成一个矩形容器，问容器最大能装多少水；而“接雨水”是让你算整个数组形成的“山谷”地形，在每一格凹陷处能接住多少雨水，最后把所有凹陷处的水量加起来。
可以这样理解：盛水容器是一个“孤儿”容器，只考虑两根柱子；接雨水是一个“连片”地形，要考虑整条轮廓线。接雨水的常见解法有单调栈、双指针和动态规划，双指针思路虽然也有，但逻辑比这题复杂很多，因为要分别维护左边最大高度和右边最大高度。
建议不要在同一天连续刷这两道题，除非你有意对比。否则很容易把“移动较低边”的容器解法，套用到接雨水里，导致状态算错。先把容器这题彻底搞懂，再去做接雨水，你会感觉思维是递进的。
4.3 面试时怎么把这题答成加分项
面试官如果问你“怎么做”，不要只甩出双指针代码，而是按这个顺序表达：
先说我有一个暴力枚举思路，枚举所有(i, j)组合，时间复杂度 O(n²)，空间 O(1)。然后说，进一步观察面积公式min(height[i], height[j]) * (j - i)，当宽度收缩时，只有提高短边才有机会让面积变大。于是可以用两个指针从两端向中间移动，每次移动较短的边，因为较短边限制了当前容器的高度，移动较长边不可能让面积增大。最后补充一句正确性证明：如果左边界是短边，那么所有以它为左边界、右指针继续向左的组合，面积都会被当前面积压倒，所以可以安全排除。
这个回答最加分的地方是证明那一段。很多人能写代码，但说不出“为什么”，一旦你能用不等式把剪枝逻辑讲清楚，面试官很容易判断出你是真懂而不是背题。最后还可以主动提一下边界情况，比如数组长度小于 2 时返回 0，时间复杂度 O(n)，空间 O(1)。整个回答控制在 3 分钟左右最合适。
5. 双指针思想与个人刷题心得
5.1 双指针还能用在哪些场景
“盛最多水的容器”是双指针思想的一个绝佳载体。类似的两端向中间移动的双指针题还有很多，比如有序数组的两数之和、判断回文字符串、反转数组、三数之和里的去重逻辑等。它们的共同特征是：状态空间是一个二维矩阵，但每走一步都能根据单调性排除一整行或一整列。
我给一个经验判断：如果你发现题目是“在一个数组里找两个元素，满足某个条件，并且条件随着两个下标的距离变化存在单调性”，就可以试试双指针。不用硬背，而是反复体会“排除不可能域”的本质。
双指针还有另一种形态，就是快慢指针，常用于链表问题，比如判断链表是否有环、找链表中点。虽然形式上不是左右夹逼，但思想依然是“用不同速度的指针在某种结构上移动，减少不必要的重复扫描”。学会了这题的左右指针，再碰快慢指针就不会觉得陌生。
5.2 踩过坑之后的几点体会
我在实际刷题中最大的体会是：不要以为自己看懂了题解，就真的会了。尤其是双指针这种“代码短到不像算法题”的类型，特别容易让人产生“我懂了”的错觉。我建议你看完题解后，把页面关掉，自己从头写一遍；写不出来，再回去看，隔一天再重写。写三遍，感觉完全不同。
另外一个很实用的方法是“费曼学习法”：把这道题的思路讲给你身边不刷题的人听，或者讲给空气听。如果你能说清楚为什么移动短边不会漏答案，而不是只说“因为大家都这么做”，那才算过关。讲不出来就去重新看证明，补上逻辑缺口。
最后想提醒一点：刷这种经典题，不要只追求提交通过。把暴力解法、最优解法、正确性证明、复杂度分析、测试边界拉通一遍，才会变成你自己的东西。一道题吃透，胜过十道题走马观花。
