接雨水：栈与双指针
同时使用计算水平层的单调栈方法和计算垂直柱的双指针方法解决接雨水问题。
接雨水：栈与双指针 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
问题：接雨水
接雨水（LeetCode 42）是最经典的面试问题之一。给定表示高度图的 n 个非负整数，其中每根柱子的宽度为 1，请计算下雨后柱子之间可以积存多少水。水会填满两侧都有更高柱子的凹谷。
对于每个位置 i，水位为 min(max_left[i], max_right[i]) - height[i]。如果结果为负数，则没有积水（因为柱子高于至少一个边界）。共有三种方法：预计算数组 O(n)/O(n)、双指针 O(n)/O(1)，以及单调栈 O(n)/O(n)。
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
# Water trapped at each position:
# pos 2: min(1,3)-0=1
# pos 4: min(2,3)-1=1
# pos 5: min(2,3)-0=2
# pos 6: min(2,3)-1=1
# pos 9: min(3,2)-1=1
# Total = 6
print('height:', height)
print('Expected trapped water: 6')
# Visualise
max_h = max(height)
for row in range(max_h, 0, -1):
line = ''
for h in height:
line += '#' if h >= row else ' '
print(line)方法 1：预计算最大值数组
一种直接的 O(n) 时间、O(n) 空间解法会预先计算两个数组：max_left[i] = 从索引 0 到 i 的最大高度，max_right[i] = 从索引 i 到 n-1 的最大高度。位置 i 的积水量为 max(0, min(max_left[i], max_right[i]) - height[i])。
构建 max_left 需要进行一次从左到右的遍历；构建 max_right 需要进行一次从右到左的遍历。最后再进行一次遍历，将积水量相加。这种方法清晰且易于解释，但需要 O(n) 的额外空间。
def trap_prefix(height):
n = len(height)
if n < 3:
return 0
max_left = [0] * n
max_right = [0] * n
max_left[0] = height[0]
for i in range(1, n):
max_left[i] = max(max_left[i-1], height[i])
max_right[-1] = height[-1]
for i in range(n-2, -1, -1):
max_right[i] = max(max_right[i+1], height[i])
water = 0
for i in range(n):
water += max(0, min(max_left[i], max_right[i]) - height[i])
return water
print(trap_prefix([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_prefix([4,2,0,3,2,5])) # 9方法 2：双指针（O(1) 空间）
双指针方法实现了 O(n) 时间和O(1) 空间。使用从两端开始的左指针和右指针。维护 max_left 和 max_right，分别表示从两侧到当前位置为止见过的最大值。
每一步处理当前最大值较小的一侧——因为这一侧是限制因素。如果 max_left < max_right，左指针位置的积水量为 max_left - height[left]（右侧足够高）。然后将左指针向内移动。否则，以对称方式处理右指针。不需要预计算数组。
def trap_two_pointer(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left] # new max on the left
else:
water += max_left - height[left] # trapped by max_left
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap_two_pointer([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_two_pointer([4,2,0,3,2,5])) # 9
print(trap_two_pointer([3,0,3])) # 3双指针为何有效：不变量
关键洞察是：当我们因为 height[left] < height[right] 而处理左指针时，可以知道 max_right >= height[right] > height[left]。因此，右侧的有效积水边界至少为 height[right]，而它已经大于 max_left。所以 min(max_left, effective_max_right) = max_left，积水公式可以简化为 max_left - height[left]。
我们不需要知道确切的 max_right——只需知道它至少为 height[right] > height[left]，就足以使用 max_left 作为水位。这就是使 O(1) 空间成为可能的优雅不变量。
# Trace two-pointer on [4, 2, 0, 3, 2, 5]
height = [4, 2, 0, 3, 2, 5]
left, right = 0, len(height) - 1
max_l = max_r = water = 0
print('height:', height)
print(f'{'Step':5} {'L':3} {'R':3} {'maxL':5} {'maxR':5} {'water':6} {'total':6}')
step = 0
while left < right:
side = 'L' if height[left] < height[right] else 'R'
if side == 'L':
if height[left] >= max_l: max_l = height[left]
else:
w = max_l - height[left]; water += w
left += 1
else:
if height[right] >= max_r: max_r = height[right]
else:
w = max_r - height[right]; water += w
right -= 1
step += 1
print(f'{step:5} {left:3} {right:3} {max_l:5} {max_r:5} {water:6}')
print('Total trapped:', water)方法 3：单调栈（水平层）
单调栈方法计算相邻柱子之间水平层中的积水。维护一个按索引排列的单调递减栈。当柱子 i 高于栈顶 j 时，会形成一个洼地：底部高度为 height[j]，弹出 j 后左侧墙高为 height[stack[-1]]，右侧墙高为 height[i]。积水会填充到 min(left_wall, right_wall) - floor 的高度，宽度为 i - stack[-1] - 1。
每个“洼地”都会在遇到更高的柱子时计算。这种方法会将积水处理为有界的矩形区段；当您还需要跟踪哪些柱子对水位有贡献时，这一点很有用。
def trap_stack(height):
stack = [] # monotonic decreasing indices
water = 0
for i in range(len(height)):
while stack and height[stack[-1]] < height[i]:
bottom_idx = stack.pop() # the floor of the valley
if not stack:
break # no left wall, no water
left_idx = stack[-1]
floor = height[bottom_idx]
water_height = min(height[left_idx], height[i]) - floor
width = i - left_idx - 1
water += water_height * width
stack.append(i)
return water
print(trap_stack([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_stack([4,2,0,3,2,5])) # 9跟踪单调栈
下面使用栈方法跟踪 [0,1,0,2,1,0,1,3,...]。在 i=3 处遇到柱子 3（h=2）时，栈顶是 i=2（h=0），将其弹出。左侧墙是 i=1（h=1），右侧墙高为 h=2。积水高度 = min(1,2)-0=1，宽度 = 3-1-1=1，面积 = 1。继续处理：栈顶 i=1（h=1）不小于 2，因此停止。将 3 入栈。
栈方法比双指针更复杂，但它能揭示每个积水单元格由哪些具体柱子形成。这一洞察对于后续重建积水布局或统计不同洼地数量的问题很有用。
def trap_stack_trace(height):
stack = []
water = 0
for i in range(len(height)):
print(f'i={i} h={height[i]}: stack={[height[s] for s in stack]}')
while stack and height[stack[-1]] < height[i]:
bot = stack.pop()
if not stack:
print(f' Pop {height[bot]}: no left wall, skip')
break
left = stack[-1]
h = min(height[left], height[i]) - height[bot]
w = i - left - 1
water += h * w
print(f' Pop {height[bot]}: floor={height[bot]}, left_wall={height[left]}, right_wall={height[i]}, h={h}, w={w}, +{h*w}')
stack.append(i)
return water
result = trap_stack_trace([0,1,0,2,1,0,1,3,2,1,2,1])
print('Total:', result)比较三种方法
三种接雨水方法总结：
- 前缀数组：时间复杂度 O(n)，空间复杂度 O(n)。最容易理解和验证。适合重视清晰度而非空间效率的面试。
- 双指针：时间复杂度 O(n)，空间复杂度 O(1)。时间和空间均达到最优。适合回答“能否做到 O(1) 空间？”之类的追问。
- 单调栈：时间复杂度 O(n)，空间复杂度 O(n)。按水平层处理积水。当您需要知道哪些柱子对积水有贡献，或该问题作为更大型的栈算法中的子问题出现时，这种方法最合适。
height = [0,1,0,2,1,0,1,3,2,1,2,1]
# All three methods — verify they agree
def trap_prefix(h):
n = len(h)
ml = [0]*n; mr = [0]*n; ml[0]=h[0]; mr[-1]=h[-1]
for i in range(1,n): ml[i]=max(ml[i-1],h[i])
for i in range(n-2,-1,-1): mr[i]=max(mr[i+1],h[i])
return sum(max(0,min(ml[i],mr[i])-h[i]) for i in range(n))
def trap_two_ptr(h):
l,r,ml,mr,w = 0,len(h)-1,0,0,0
while l<r:
if h[l]<h[r]:
ml=max(ml,h[l]); w+=ml-h[l]; l+=1
else:
mr=max(mr,h[r]); w+=mr-h[r]; r-=1
return w
def trap_stk(h):
stk,w = [],[]
for i in range(len(h)):
while stk and h[stk[-1]]<h[i]:
b=stk.pop()
if not stk: break
w.append(max(0,min(h[stk[-1]],h[i])-h[b])*(i-stk[-1]-1))
stk.append(i)
return sum(w)
for h in [height, [4,2,0,3,2,5], [3,0,3], [1,0,1]]:
p=trap_prefix(h); t=trap_two_ptr(h); s=trap_stk(h)
print(f'{h}: prefix={p}, two-ptr={t}, stack={s}, match={p==t==s}')盛最多水的容器
盛最多水的容器（LeetCode 11）经常与接雨水问题混淆。在这里，您必须选择恰好两根柱子，水只由这两根柱子限定（不考虑内部柱子）。最大化面积 min(height[l], height[r]) × (r - l)。
双指针可以用贪心方式解决此问题：从两端开始（此时宽度最大）。将较短的指针向内移动——移动较高的指针只会减小面积。该方法的时间复杂度为 O(n)，空间复杂度为 O(1)；它比接雨水的双指针方法更简单，因为不需要维护运行中的最大值。
def max_water_container(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
# Move the shorter bar: moving taller bar can only reduce min
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
print(max_water_container([1,8,6,2,5,4,8,3,7])) # 49: bars 8 and 7
print(max_water_container([1,1])) # 1
print(max_water_container([4,3,2,1,4])) # 16
# Key difference from trapping rain water:
# Container: choose 2 bars, water fills freely between them (no internal barriers)
# Trapping: water fills ALL valleys in the full elevation map进阶：接雨水 II（三维）
接雨水 II（LeetCode 407）扩展到了二维高度矩阵。水可以向四个方向流动，并且必须越过边界流出。解决方案使用最小堆：先将所有边界单元格加入堆中，然后执行类似 BFS 的扩展。处理高度最小的单元格——任何更低的邻居至少都能积蓄当前单元格水位高度的水。
这与一维情况的算法有本质区别，同时考查堆操作和 BFS 遍历。一维双指针技巧无法推广到二维；堆方法可以。
import heapq
def trap_rain_water_2d(heightMap):
if not heightMap or not heightMap[0]:
return 0
m, n = len(heightMap), len(heightMap[0])
visited = [[False]*n for _ in range(m)]
heap = [] # (height, row, col)
# Add all border cells to the heap
for i in range(m):
for j in [0, n-1]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
for j in range(n):
for i in [0, m-1]:
if not visited[i][j]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
total = 0
max_h = 0
while heap:
h, r, c = heapq.heappop(heap)
max_h = max(max_h, h)
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0<=nr<m and 0<=nc<n and not visited[nr][nc]:
visited[nr][nc] = True
total += max(0, max_h - heightMap[nr][nc])
heapq.heappush(heap, (max(max_h, heightMap[nr][nc]), nr, nc))
return total
map2d = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
print(trap_rain_water_2d(map2d)) # 4面试中何时使用各方法
接雨水面试题的决策指南：
- 从以下方法开始：前缀数组——容易解释，直观清晰，正确性明确
- 追问“空间复杂度能做到 O(1) 吗？”：双指针——解释较小一侧是瓶颈这一不变量
- 如果面试官问“还有其他方法吗？”：单调栈——解释水平层的计算方式
在开始编写代码之前，务必先清楚定义每个位置的水位由什么决定（两侧最高柱子高度中的较小值）。这能体现您对问题的理解，也让解法更容易解释。
# Quick summary of all three approaches
approaches = [
{
'name': 'Prefix max arrays',
'time': 'O(n)', 'space': 'O(n)',
'description': '3 passes: build max_left, max_right, sum water column-by-column',
},
{
'name': 'Two pointers',
'time': 'O(n)', 'space': 'O(1)',
'description': 'Process smaller side: its max is the limiting wall, no array needed',
},
{
'name': 'Monotonic stack',
'time': 'O(n)', 'space': 'O(n)',
'description': 'Compute water in horizontal layers when a taller bar is encountered',
},
]
for a in approaches:
print(f'{a["name"]} [{a["time"]} / {a["space"]}]')
print(f' {a["description"]}')
print()边界情况和常见错误
接雨水问题中的常见错误：
- 忘记取最小值：水位是
min(max_left, max_right)，不能只取其中一个值。柱子两侧都需要有足够高的墙。 - 积水为负：当某个位置的高度超过水位时，使用
max(0, ...)将负值限制为 0。 - 边缘位置：最左和最右的柱子永远无法积水（一侧没有墙）。前缀数组方法会自然处理这一点，因为
max_left[0] = height[0]会使索引 0 处的积水始终为 0。 - 空数组或过小的数组：对于元素少于 3 个的数组，返回 0。
def trap(height):
n = len(height)
if n < 3:
return 0 # need at least 3 bars to trap anything
left, right = 0, n - 1
max_l = max_r = water = 0
while left < right:
if height[left] <= height[right]:
if height[left] >= max_l:
max_l = height[left]
else:
water += max_l - height[left] # never negative: max_l > height[left]
left += 1
else:
if height[right] >= max_r:
max_r = height[right]
else:
water += max_r - height[right]
right -= 1
return water
# Edge cases
print(trap([])) # 0: empty
print(trap([1])) # 0: single bar
print(trap([1,2])) # 0: two bars
print(trap([3,0,3])) # 3: simple valley
print(trap([3,3,3])) # 0: flat top, no water快速测验
测试您对本课“数据结构与算法——编码面试准备”概念的理解。
课程回顾
在本课中，您学到了：接雨水问题的解法是在每个位置取左右两侧最高墙高度中的较小值；双指针 O(1) 空间方法之所以有效，是因为较矮一侧的运行最大值始终是限制条件；单调栈方法按水平层计算积水，适合与其他基于栈的逻辑结合使用。接下来我们将转向系统设计概念，从用于结构化面试回答的 RADIO 框架开始。
常见问题解答
「接雨水：栈与双指针」课时是免费的吗？
是的 — 「接雨水：栈与双指针」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「接雨水：栈与双指针」这节课中我会学到什么？
同时使用计算水平层的单调栈方法和计算垂直柱的双指针方法解决接雨水问题。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「接雨水：栈与双指针」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 单调栈：递增与递减
- 直方图中的最大矩形
- 使用单调双端队列求滑动窗口最大值
- 接雨水：栈与双指针