题目描述
思路解析
一句话答案：LeetCode 42 接雨水的最优解是对撞双指针：左右各一个指针往中间走，同时维护左边最高墙 leftMax 和右边最高墙 rightMax，每轮只结算较矮的那一端——该格接水量等于对应一侧的最高墙减自身高度。每格只被访问一次，时间 O(n)、空间 O(1)，优于按列扫描的 O(n²) 和预处理数组的 O(n) 空间做法。
接雨水这道题在问什么
给一排宽度为 1、高度不等的柱子，下雨后凹槽里会存水，求总共能接多少格水。关键的物理直觉是按「竖列」看：某一列上方能存的水，取决于它左边的最高柱和右边的最高柱——水面高度是两者中较矮的那个，再减去这一列自身的高度，就是这一列的储水量；如果自身比两边最高墙还高，这一列存不了水。
从每列扫两遍到双指针的推导
把上面的直觉直接翻译成代码，就是对每一列分别向左、向右扫一遍找最高墙，n 列各扫 O(n)，总共 O(n²)，柱子一多就太慢。第一步优化是用两个数组预处理出「每个位置左侧最高」和「右侧最高」，查询变 O(1)，时间降到 O(n)，但要 O(n) 的额外空间。
再进一步观察：结算一列时，其实不需要同时精确知道左右两边的最高墙，只需要知道「较矮的那一边有多高」。这就是双指针版本省掉数组的突破口。
为什么只看较矮的一端就能定水量
让左指针 l 从最左、右指针 r 从最右往中间走，一路维护 leftMax（l 左侧走过的最高柱）和 rightMax（r 右侧走过的最高柱）。每轮比较两端柱高：假设左端更矮，那么右边一定存在一根不低于当前右端的柱子挡着，水面下限已经被左侧锁死——这一格的水量就是 leftMax 减去自身高度，跟右边究竟多高无关。右端更矮时对称处理。
这就是「木桶短板」的贪心论证：较矮的一端是当前的瓶颈，它的储水量当场可以拍板，所以放心结算并把该指针往中间挪一格。每格恰好被结算一次，两个指针合计走完整个数组，正确性和 O(n) 的效率同时成立。
循环里最容易写错的三个地方
一是减错基准：某格的水量是「一侧最高墙减自身」，不是拿相邻柱子或自身高度做差；二是指针移动方向：每轮必须移较矮的那一端，若总是移左指针，右侧瓶颈没被结算就被跳过，答案偏小；三是判断顺序：当前柱不低于本侧 max 时它自己就是新墙，要先更新 max 且这一格不接水，只有严格矮于 max 才累加 max 减自身。
复杂度与另一条单调栈思路
双指针版时间 O(n)：l 和 r 相向而行，每格只处理一次；空间 O(1)：全程只有 l、r、leftMax、rightMax 和累加器五个变量。
这道题还有一条按「横条」结算的思路——单调递减栈：遇到比栈顶高的柱子就出栈结算一层横向的水。同样是 O(n) 时间，但要 O(n) 的栈空间。面试里双指针是空间最优解，单调栈则更适合作为理解「按层算水」的补充视角，两种都值得会讲。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
双指针的妙处：从两端往中间走，只盯当前较矮的一侧，就能现场定出这格的水，不必每格都向两边扫一遍。
初始：l 指向最左(下标 0)，r 指向最右(下标 11)。leftMax/rightMax 先记 0。 谁矮谁先决定接水。
左端较矮(高 0 < 右端 1)。它比左墙 leftMax 还高 → 它就是新左墙 leftMax=0，自身接不到水。
左侧处理完，l 右移到下标 1。继续比较两端。
右端较矮或持平(高 1 ≤ 左端 1)。它比右墙 rightMax 还高 → 它就是新右墙 rightMax=1，自身接不到水。
右侧处理完，r 左移到下标 10。继续比较两端。
左端较矮(高 1 < 右端 2)。它比左墙 leftMax 还高 → 它就是新左墙 leftMax=1，自身接不到水。
左侧处理完，l 右移到下标 2。继续比较两端。
左端较矮(高 0 < 右端 2)。左墙 leftMax=1 比它高 → 这格接水 1-0=1。累计 1。
左侧处理完，l 右移到下标 3。继续比较两端。
右端较矮或持平(高 2 ≤ 左端 2)。它比右墙 rightMax 还高 → 它就是新右墙 rightMax=2，自身接不到水。
右侧处理完，r 左移到下标 9。继续比较两端。
右端较矮或持平(高 1 ≤ 左端 2)。右墙 rightMax=2 比它高 → 这格接水 2-1=1。累计 2。
右侧处理完，r 左移到下标 8。继续比较两端。
右端较矮或持平(高 2 ≤ 左端 2)。它比右墙 rightMax 还高 → 它就是新右墙 rightMax=2，自身接不到水。
右侧处理完，r 左移到下标 7。继续比较两端。
左端较矮(高 2 < 右端 3)。它比左墙 leftMax 还高 → 它就是新左墙 leftMax=2，自身接不到水。
左侧处理完，l 右移到下标 4。继续比较两端。
左端较矮(高 1 < 右端 3)。左墙 leftMax=2 比它高 → 这格接水 2-1=1。累计 3。
左侧处理完，l 右移到下标 5。继续比较两端。
左端较矮(高 0 < 右端 3)。左墙 leftMax=2 比它高 → 这格接水 2-0=2。累计 5。
左侧处理完，l 右移到下标 6。继续比较两端。
左端较矮(高 1 < 右端 3)。左墙 leftMax=2 比它高 → 这格接水 2-1=1。累计 6。
左侧处理完，l 右移到下标 7。继续比较两端。
两指针相遇，全部处理完。所有蓝色水柱加起来 = 6，就是这排柱子能接住的总水量。
边界先想清：没有“两边都更高”的格子就接不到水。
面试最常被追问的两点。
参考代码
def trap(height): l, r = 0, len(height) - 1 lmax = rmax = total = 0 while l < r: if height[l] < height[r]: if height[l] >= lmax: lmax = height[l] else: total += lmax - height[l] l += 1 else: if height[r] >= rmax: rmax = height[r] else: total += rmax - height[r] r -= 1 return total复杂度
- 时间：O(n)，左右指针合计走一遍
- 空间：O(1)，只用 l/r/leftMax/rightMax 几个变量
易错点
面试追问把动画讲成自己的话
追问为什么每次移动“较矮”的那一端是对的？
追问还有哪些解法？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
移动零
LeetCode 283 · 简单 · 沿着 双指针 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题