☔️ 从生活场景到算法难题：彻底搞懂「接雨水」问题
你有没有在暴雨天观察过窗外的排水管道？有没有注意到，当雨水落在高低不平的地面上时，会在低洼处积蓄起来？这看似平常的自然现象，却衍生出了一道风靡算法圈的经典难题——「接雨水」问题。这道题不仅频繁出现在大厂面试中，更是考察算法思维的绝佳案例。今天，就让我们一起从问题本质出发，一步步拆解这道经典数组难题。
📖 问题定义：到底什么是「接雨水」？
在正式开始分析前，我们先明确问题的具体描述：
给定
n个非负整数表示每个宽度为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 个单位的雨水（蓝色部分表示雨水）。
从这个例子中，我们可以提炼出问题的核心矛盾：雨水能积蓄的条件，是当前位置的左右两侧都有比它高的柱子。这就像是一个木桶，能装多少水取决于最短的那块木板。而在「接雨水」问题中，每个位置能积蓄的雨水量，则取决于左右两侧最高柱子中的较小值，减去当前柱子的高度。
🧠 思维突破：从暴力到高效的进化之路
接下来，我们将从最直观的暴力解法开始，逐步优化算法的时间复杂度，最终达到最优解。这个过程不仅能帮助我们理解问题的本质，更能锻炼我们的算法思维。
🔹 暴力解法：直观但低效的起点
核心思路：对于每个位置，分别找到其左右两侧的最高柱子，然后计算该位置能积蓄的雨水量，最后将所有位置的雨水量相加。
代码实现：
def trap(height):
n = len(height)
if n < 3:
return 0 # 至少需要3个柱子才能接雨水
total_water = 0
for i in range(1, n-1):
# 找到左侧最高柱子
left_max = max(height[:i])
# 找到右侧最高柱子
right_max = max(height[i+1:])
# 计算当前位置能接的雨水量
current_water = min(left_max, right_max) - height[i]
if current_water > 0:
total_water += current_water
return total_water
复杂度分析：
- 时间复杂度：O(n²)，因为对于每个位置，我们都需要遍历其左右两侧的所有元素来找到最高柱子。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
优缺点：
- 优点：思路直观，容易理解和实现。
- 缺点：时间复杂度较高，当输入规模较大时，算法效率会急剧下降。
🔹 动态规划：预处理优化时间复杂度
核心思路：暴力解法的瓶颈在于，对于每个位置都需要重复计算左右两侧的最高柱子。我们可以通过动态规划的方式，预先计算出每个位置的左右最高柱子高度，从而将时间复杂度优化到O(n)。
具体步骤：
- 从左到右遍历数组，计算每个位置的左侧最高柱子高度，存储在
left_max数组中。 - 从右到左遍历数组，计算每个位置的右侧最高柱子高度，存储在
right_max数组中。 - 遍历数组，对于每个位置，计算其能积蓄的雨水量，并累加到总雨水量中。
代码实现：
def trap(height):
n = len(height)
if n < 3:
return 0
total_water = 0
left_max = [0] * n
right_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[-1] = height[-1]
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1], height[i])
# 计算总雨水量
for i in range(n):
current_water = min(left_max[i], right_max[i]) - height[i]
total_water += current_water
return total_water
复杂度分析：
- 时间复杂度：O(n)，只需要三次遍历数组。
- 空间复杂度：O(n)，需要额外的两个数组来存储左右最高柱子高度。
优缺点：
- 优点：时间复杂度优化到了线性级别，效率较高。
- 缺点：需要额外的空间来存储预处理结果。
🔹 双指针法：空间优化的终极形态
核心思路：在动态规划的基础上，我们可以进一步优化空间复杂度。通过使用双指针，我们可以在一次遍历中完成左右最高柱子的计算和雨水量的累加，从而将空间复杂度优化到O(1)。
关键观察：
- 当
left_max < right_max时，左侧的最高柱子是决定当前位置雨水量的关键，因为右侧存在更高的柱子，能保证雨水不会从右侧流走。 - 反之，当
right_max <= left_max时，右侧的最高柱子是决定当前位置雨水量的关键。
代码实现：
def trap(height):
n = len(height)
if n < 3:
return 0
total_water = 0
left, right = 0, n-1
left_max, right_max = 0, 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
复杂度分析：
- 时间复杂度：O(n)，只需要一次遍历数组。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
优缺点：
- 优点：时间和空间复杂度都达到了最优，是这道题的终极解法。
- 缺点：思路相对抽象，需要一定的理解成本。
🔹 单调栈法：从另一个角度看问题
核心思路：除了上述方法外，我们还可以使用单调栈来解决这道题。单调栈的核心思想是，维护一个单调递减的栈，当遇到比栈顶元素高的柱子时，说明找到了一个可以接雨水的凹槽。
具体步骤：
- 遍历数组，将柱子的索引压入栈中，保持栈内元素对应的柱子高度单调递减。
- 当遇到比栈顶元素高的柱子时，弹出栈顶元素作为凹槽的底部。
- 此时，栈顶元素即为凹槽的左侧柱子，当前遍历到的柱子即为凹槽的右侧柱子。
- 计算凹槽的宽度和高度，从而得到该凹槽能积蓄的雨水量。
代码实现：
def trap(height):
n = len(height)
if n < 3:
return 0
total_water = 0
stack = []
for i in range(n):
while stack and height[i] > height[stack[-1]]:
# 弹出栈顶元素作为凹槽底部
bottom = stack.pop()
if not stack:
break # 栈为空，说明没有左侧柱子，无法接雨水
# 计算凹槽的宽度和高度
left = stack[-1]
width = i - left - 1
current_height = min(height[left], height[i]) - height[bottom]
total_water += width * current_height
stack.append(i)
return total_water
复杂度分析：
- 时间复杂度：O(n)，每个柱子最多入栈和出栈一次。
- 空间复杂度：O(n)，最坏情况下，栈需要存储所有柱子的索引。
优缺点：
- 优点：从另一个角度理解问题，思路新颖。
- 缺点：代码实现相对复杂，不易理解。
🎯 总结：从问题到解法的思维路径
通过以上分析，我们可以看到，解决「接雨水」问题的关键在于理解雨水积蓄的条件：每个位置能积蓄的雨水量，取决于左右两侧最高柱子中的较小值，减去当前柱子的高度。围绕这个核心条件，我们可以演化出多种解法：
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 暴力解法 | O(n²) | O(1) | 思路直观，容易理解 | 效率低下，不适用于大数据 |
| 动态规划 | O(n) | O(n) | 效率较高，容易实现 | 需要额外的存储空间 |
| 双指针法 | O(n) | O(1) | 时间和空间复杂度最优 | 思路相对抽象 |
| 单调栈法 | O(n) | O(n) | 从新角度理解问题 | 代码实现复杂 |
在实际应用中，我们可以根据具体场景选择合适的解法。如果追求代码的简洁和易读性，动态规划是不错的选择；如果追求最优的空间复杂度，双指针法则是最佳选择；而单调栈法则能帮助我们从另一个角度理解问题，拓宽算法思维。
