读完本文你将了解盛最多水容器的最优解法 | 从暴力到双指针的优化过程 | 面试中的表现要点 题目给定一个非负整数数组 height每个元素代表坐标 (i, height[i]) 处的一条垂线。找出两条线使它们与 x 轴共同构成的容器能够容纳最多的水。项目说明输入height [1,8,6,2,5,4,8,3,7]输出49约束n height.length2 ≤ n ≤ 10⁵0 ≤ height[i] ≤ 10⁴ 先问一个问题这题在 LeetCode 上被点了 23 万次赞排进 Top 50 热门题。看起来简单——不就是找两个柱子算面积嘛——但 90% 的人第一次写的解法放到 10⁵ 长度的数组上会直接跑死。猜猜 AI 第一次会怎么写 第一版AI 的朴素解法暴力枚举AI 遇到找两个东西的问题第一反应永远是嵌套循环defmax_area(height): 暴力法穷举所有柱子组合 nlen(height)max_water0foriinrange(n):forjinrange(i1,n):hmin(height[i],height[j])wj-i areah*w max_watermax(max_water,area)returnmax_water这版代码逻辑没问题。问题出在复杂度上时间复杂度O(n²)空间复杂度O(1)放到一个 10⁵ 个元素的数组上要执行约 50 亿次计算。不是慢一点的问题——是面试官直接喊停的水平。不过暴力解给出了一个重要的观察面积 min(左高度, 右高度) × (右下标 - 左下标)这个公式告诉我们面积受制于较短的那根柱子。 AI 的自我优化提示 AI 优化一下后它往往会经历一个思考过程第 1 次提示思路转变“既然面积受限于较短的那根那我试试从两边往中间走”defmax_area(height): 两指针从两端向中间移动 left,right0,len(height)-1max_water0whileleftright:hmin(height[left],height[right])wright-left max_watermax(max_water,h*w)ifheight[left]height[right]:left1else:right-1returnmax_water关键优化点每次只移动较短的那端——因为面积受限于短板移动长板不可能得到更大的面积。时间复杂度O(n)空间复杂度O(1)暴力枚举O(n²)双指针O(n)证明移动短板才可能增大面积☕ Java 实现publicintmaxArea(int[]height){intleft0,rightheight.length-1;intmaxWater0;while(leftright){inthMath.min(height[left],height[right]);intwright-left;maxWaterMath.max(maxWater,h*w);if(height[left]height[right]){left;}else{right--;}}returnmaxWater;}第 2 次提示证明它AI 不会只满足于看起来对继续追问后它会给出一个直观证明假设 left0, rightn-1且 height[left] height[right]如果移动 left短板新面积可能变大也可能变小如果移动 right长板新面积一定 ≤ 当前面积宽变小了高受限于依然不变的 left 短板结论移动短板不一定变大但移动长板一定不会变大。所以策略就是——谁短移谁。左右左右left rightleft right开始left0, rightn-1比较两端高度左指针右移left右指针左移right--计算面积更新最大值结束返回最大面积 算法模式拆解这道题属于Two Pointers双指针模式中的相向双指针子类。适用场景需要在一维数组中找两个元素且满足某种约束条件时尝试从两端向中间逼近。核心特征数组有一定顺序不一定已排序需要比较两个元素可以证明移动某一边不会丢失最优解同类题三数之和Three Sum固定一个指针另外两个相向移动接雨水Trapping Rain Water双指针加强版需要记录左右最大值️ 真实产品场景这道题在产品环境中的威力远比你在 LeetCode 上感受到的大。场景一物流中的最优路线规划你在做物流调度系统要从 A 地运一批货到 B 地。每个站点有不同的装卸能力就是 height你需要选两个站点之间的最优运输路径。运力受限于较小站点的处理能力短板效应而距离越远路线成本越高——完全就是盛水容器的问题变形。实际中可能同时有几千个站点参与调度O(n) 和 O(n²) 的差距——前者毫秒级出结果后者等几分钟都可能行。场景二数据库连接池的并发分配数据库连接数受限于最小节点的并发能力短板每个连接池的实例位置就是下标。分配连接时策略同样是找两个节点使有效吞吐量最大化——这就是双指针的活。✅ 面试官的点评维度合格线加分项理解题意能说清面积公式明确指出短板效应暴力解写出 O(n²)主动分析复杂度瓶颈双指针写出双指针代码证明为什么移动短板才可能变大边界情况处理 n2测试全升序/全降序数组扩展无能引出三数之和同类题常见踩坑只想着枚举不提优化——面试官会问还能更好吗写双指针但说不清为什么是对的——能写对不代表理解透忽略了大数溢出的可能性——如果 height 是 int 但面积用 int 存可能溢出 同类题推荐三数之和LeetCode 15双指针 排序固定一个再移动两个接雨水LeetCode 42双指针进阶版维护左右最大值的 trick有效三角形的个数LeetCode 611也是固定一个双指针扫描来源说明✅ 已验证LeetCode 官方题解 AI 实测✅ 代码已实测通过 LeetCode 测试用例