引言：为什么“接雨水”是算法面试的必考题
在LeetCode等算法面试平台上，”Trapping Rain Water”（接雨水）是一个非常经典的题目。它不仅仅是一个简单的数组操作问题，而是一个能够全面考察面试者算法思维、数据结构理解和代码优化能力的综合性问题。
这个问题的难度在于它提供了多种解法，从暴力解法到双指针，再到动态规划和单调栈，每种解法都有其独特的思维方式和优化思路。掌握这道题不仅能够帮助你解决面试中的类似问题，更重要的是能够培养你分析问题、优化算法的能力。
本文将从最基础的暴力解法开始，逐步深入到双指针、动态规划和单调栈三种核心优化技巧，帮助你彻底理解并掌握这道经典面试题。
问题描述与暴力解法
问题描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
暴力解法思路
暴力解法是最直观的思路。对于数组中的每个位置，我们计算该位置能接多少雨水。一个位置能接的雨水量取决于该位置左边和右边柱子的最大高度中的较小值减去当前位置的高度。
具体步骤：
- 遍历数组中的每个位置
- 对于每个位置，找到左边柱子的最大高度
- 找到右边柱子的最大高度
- 该位置能接的雨水量 = min(左边最大高度, 右边最大高度) - 当前位置高度
- 将所有位置的雨水量累加
暴力解法代码实现
def trap_brute_force(height):
"""
暴力解法：对于每个位置，计算左右最大高度
时间复杂度：O(n^2)
空间复杂度：O(1)
"""
if not height:
return 0
n = len(height)
total_water = 0
for i in range(1, n-1): # 第一个和最后一个位置无法接水
# 找左边最大高度
left_max = 0
for j in range(i):
left_max = max(left_max, height[j])
# 找右边最大高度
right_max = 0
for j in range(i+1, n):
right_max = max(right_max, height[j])
# 计算当前位置能接的雨水量
current_water = min(left_max, right_max) - height[i]
if current_water > 0:
total_water += current_water
return total_water
# 测试
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(f"暴力解法结果: {trap_brute_force(height)}") # 输出: 6
暴力解法分析
优点：
- 思路简单直观，容易理解和实现
- 空间复杂度为 O(1)，不需要额外存储空间
缺点：
- 时间复杂度为 O(n^2)，对于每个位置都要遍历左右两边，效率低下
- 当数组长度较大时，会超时
适用场景：
- 数组长度较小（< 1000）
- 作为理解问题的基础思路
双指针解法：空间换时间的经典应用
双指针解法思路
双指针解法是对暴力解法的优化。我们观察到，对于每个位置，我们只需要知道左边和右边的最大高度。如果我们能同时从左向右和从右向左遍历，就可以避免重复计算。
核心思想：
- 使用两个指针 left 和 right，分别从数组的两端开始
- 维护两个变量 left_max 和 right_max，分别表示左边和右边的最大高度
- 比较 left_max 和 right_max 的大小：
- 如果 left_max < right_max，说明左边受限，left 位置的雨水量由 left_max 决定
- 如果 right_max <= left_max，说明右边受限，right 位置的雨水量由 right_max 决定
- 移动指针并更新最大高度
双指针解法代码实现
def trap_two_pointers(height):
"""
双指针解法：左右指针同时移动，维护左右最大高度
时间复杂度：O(n)
空间复杂度：O(1)
"""
if not height:
return 0
n = len(height)
left, right = 0, n - 1
left_max, right_max = 0, 0
total_water = 0
while left < right:
# 先移动较小的一边
if height[left] < height[right]:
# 左边受限
if height[left] >= left_max:
left_max = height[left] # 更新左边最大高度
else:
total_water += left_max - height[left] # 计算雨水量
left += 1
else:
# 右边受限
if height[right] >= right_max:
right_max = height[right] # 更新右边最大高度
else:
total_water += right_max - height[right] # 计算雨水量
right -= 1
return total_water
# 测试
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(f"双指针解法结果: {trap_two_pointers(height)}") # 输出: 6
height2 = [4,2,0,3,2,5]
print(f"双指针解法结果: {trap_two_pointers(height2)}") # 输出: 9
双指针解法详细分析
为什么这样移动是正确的？
关键在于理解”木桶效应”：一个位置能接多少水，取决于它左右两边的”短板”。当 height[left] < height[right] 时，说明左边是短板，left 位置的雨水量由左边的最大高度决定，因为右边有更高的柱子挡住。同理，当 height[right] <= height[left] 时，右边是短板。
时间复杂度分析：
- 只需要遍历数组一次，时间复杂度为 O(n)
空间复杂度分析：
- 只使用了常数个变量，空间复杂度为 O(1)
双指针解法的局限性：
- 虽然时间复杂度最优，但逻辑相对复杂，需要深入理解才能正确实现
- 对于某些特殊情况，可能需要额外的边界处理
动态规划解法：预处理思想的应用
动态规划解法思路
动态规划解法采用预处理的思想。我们预先计算出每个位置左边和右边的最大高度，然后在计算雨水量时直接查表。
具体步骤：
- 创建两个数组 left_max 和 right_max，长度与原数组相同
- left_max[i] 表示位置 i 左边（包括 i）的最大高度
- right_max[i] 表示位置 i 右边（包括 i）的最大高度
- 遍历数组，计算每个位置的雨水量：min(left_max[i], right_max[i]) - height[i]
动态规划解法代码实现
def trap_dynamic_programming(height):
"""
动态规划解法：预处理左右最大高度数组
时间复杂度：O(n)
空间复杂度：O(n)
"""
if not height:
return 0
n = len(height)
# 创建left_max数组
left_max = [0] * n
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], height[i])
# 创建right_max数组
right_max = [0] * n
right_max[n-1] = height[n-1]
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1], height[i])
# 计算总雨水量
total_water = 0
for i in range(1, n-1): # 第一个和最后一个位置无法接水
current_water = min(left_max[i], right_max[i]) - height[i]
if current_water > 0:
total_water += current_water
return total_water
# 测试
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(f"动态规划解法结果: {trap_dynamic_programming(height)}") # 输出: 6
# 详细过程演示
def trap_dp_detailed(height):
"""详细演示动态规划过程"""
if not height:
return 0
n = len(height)
print(f"原始数组: {height}")
# 计算left_max
left_max = [0] * n
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], height[i])
print(f"left_max: {left_max}")
# 计算right_max
right_max = [0] * n
right_max[n-1] = height[n-1]
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1], height[i])
print(f"right_max: {right_max}")
# 计算每个位置的雨水量
print("位置 | 高度 | 左max | 右max | min | 雨水量")
print("-" * 45)
total_water = 0
for i in range(1, n-1):
min_max = min(left_max[i], right_max[i])
water = min_max - height[i] if min_max > height[i] else 0
total_water += water
print(f"{i:4} | {height[i]:5} | {left_max[i]:5} | {right_max[i]:5} | {min_max:3} | {water:7}")
return total_water
# 详细演示
print("\n动态规划详细过程:")
trap_dp_detailed([0,1,0,2,1,0,1,3,2,1,2,1])
动态规划解法分析
优点：
- 时间复杂度为 O(n)，效率高
- 思路清晰，容易理解和实现
- 计算过程可复用，left_max 和 right_max 数组可以用于其他计算
缺点：
- 空间复杂度为 O(n)，需要额外的存储空间
- 需要两次遍历（计算 left_max 和 right_max）
适用场景：
- 当需要多次查询左右最大高度时
- 当空间复杂度要求不严格时
单调栈解法：从几何角度思考
单调栈解法思路
单调栈解法是从几何角度思考问题的另一种方法。我们维护一个单调递减的栈，栈中存储柱子的索引。当遇到一个比栈顶高的柱子时，说明形成了一个”坑”，可以计算雨水量。
具体步骤：
- 使用一个栈来存储柱子的索引
- 遍历数组，对于每个高度：
- 如果栈为空或当前高度 <= 栈顶高度，直接入栈
- 如果当前高度 > 栈顶高度，说明形成了凹陷，需要计算雨水量
- 计算雨水量的公式：
- 弹出栈顶元素，作为底部
- 新的栈顶元素作为左边边界
- 当前元素作为右边边界
- 雨水高度 = min(左边边界, 右边边界) - 底部高度
- 雨水宽度 = 右边边界索引 - 左边边界索引 - 1
- 雨水量 = 雨水高度 × 雨水宽度
单调栈解法代码实现
def trap_monotonic_stack(height):
"""
单调栈解法：维护单调递减的栈
时间复杂度：O(n)
空间复杂度：O(n)
"""
if not height:
return 0
stack = [] # 存储索引
total_water = 0
for i, h in enumerate(height):
# 当栈不为空且当前高度大于栈顶高度时
while stack and h > height[stack[-1]]:
# 弹出栈顶元素作为底部
bottom = stack.pop()
# 如果栈为空，说明没有左边边界
if not stack:
break
# 左边边界
left = stack[-1]
# 右边边界是当前索引 i
right = i
# 计算雨水高度
water_height = min(height[left], height[right]) - height[bottom]
# 计算雨水宽度
water_width = right - left - 1
# 累加雨水量
total_water += water_height * water_width
stack.append(i)
return total_water
# 测试
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(f"单调栈解法结果: {trap_monotonic_stack(height)}") # 输出: 6
height2 = [4,2,0,3,2,5]
print(f"单调栈解法结果: {trap_monotonic_stack(height2)}") # 输出: 9
单调栈解法详细过程演示
def trap_monotonic_stack_detailed(height):
"""详细演示单调栈过程"""
if not height:
return 0
stack = []
total_water = 0
print("索引 | 高度 | 栈状态 | 操作 | 雨水量")
print("-" * 50)
for i, h in enumerate(height):
operation = ""
water_added = 0
while stack and h > height[stack[-1]]:
bottom_idx = stack.pop()
if not stack:
operation += f"弹出{bottom_idx}(无左边界)"
break
left_idx = stack[-1]
right_idx = i
water_height = min(height[left_idx], height[right_idx]) - height[bottom_idx]
water_width = right_idx - left_idx - 1
water = water_height * water_width
operation += f"弹出{bottom_idx}, 计算[{left_idx},{right_idx}]={water} "
water_added += water
if operation == "":
operation = "入栈"
stack.append(i)
print(f"{i:4} | {h:5} | {stack} | {operation} | {water_added}")
return total_water
# 详细演示
print("\n单调栈详细过程:")
trap_monotonic_stack_detailed([0,1,0,2,1,0,1,3,2,1,2,1])
单调栈解法分析
优点：
- 时间复杂度为 O(n)，每个元素最多入栈出栈一次
- 从几何角度理解问题，直观形象
- 可以处理更复杂的接雨水问题（如 LeetCode 42 的变种）
缺点：
- 逻辑相对复杂，需要理解单调栈的工作原理
- 代码实现容易出错，特别是边界条件的处理
适用场景：
- 需要处理更复杂的接雨水问题
- 面试中展示不同的解题思路
四种解法对比总结
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 暴力解法 | O(n²) | O(1) | 思路简单 | 效率低 |
| 双指针 | O(n) | O(1) | 空间最优 | 逻辑复杂 |
| 动态规划 | O(n) | O(n) | 思路清晰 | 需要额外空间 |
| 单调栈 | O(n) | O(n) | 几何直观 | 实现复杂 |
面试技巧与常见问题
面试中的考察点
- 基础理解：能否理解问题本质，找到正确的计算公式
- 优化思路：能否从暴力解法出发，逐步优化到最优解
- 代码实现：能否写出 bug-free 的代码，处理边界情况
- 复杂度分析：能否正确分析时间空间复杂度
- 扩展思考：能否举一反三，处理变种问题
常见面试问题
Q1: 为什么双指针解法中，移动较小的一边？ A: 因为木桶效应，接水量由较短的板决定。移动较小的一边可以确保我们总是基于当前已知的”短板”来计算雨水量。
Q2: 动态规划解法中，为什么需要两个数组？ A: 因为每个位置的雨水量取决于左右两边的最大高度，需要预先计算并存储这些信息以避免重复计算。
Q3: 单调栈解法中，栈中存储的是什么？ A: 存储的是柱子的索引，而不是高度。这样可以在计算雨水量时同时获取位置信息和高度信息。
Q4: 这些解法可以扩展到其他问题吗？ A: 可以。例如：
- 接雨水 II（二维版本）可以使用优先队列
- 柱状图中最大矩形面积可以使用单调栈
- 类似几何问题都可以借鉴这些思路
实战练习与进阶
练习题目推荐
- LeetCode 42. 接雨水（基础）
- LeetCode 407. 接雨水 II（二维扩展）
- LeetCode 84. 柱状图中最大的矩形（单调栈应用）
- LeetCode 85. 最大矩形（二维单调栈）
- LeetCode 238. 除自身以外数组的乘积（类似预处理思想）
进阶技巧
- 空间优化：动态规划解法可以进一步优化为双指针，达到 O(1) 空间
- 多维度扩展：思考三维空间中的接雨水问题
- 变种问题：考虑有障碍物、不规则形状等情况
- 数学证明：尝试用数学归纳法证明解法的正确性
总结
接雨水问题是算法面试中的经典题目，通过这道题我们可以学习到多种重要的算法思想：
- 暴力解法：培养问题分析能力
- 双指针：学习空间优化技巧
- 动态规划：掌握预处理思想
- 单调栈：理解数据结构的应用
掌握这四种解法，不仅能够应对面试中的接雨水问题，更重要的是能够培养算法思维，为解决其他复杂问题打下坚实基础。在实际面试中，建议先给出暴力解法，然后逐步优化，展示完整的思考过程，这样更能体现你的算法能力。
记住，算法学习不是死记硬背，而是理解每种方法背后的思想和适用场景。希望这篇详细的教程能够帮助你彻底掌握接雨水问题，在面试中游刃有余！