【力扣-42. 接雨水】Python笔记

题目回顾

题目编号：42
题目名称：接雨水
题目难度：困难
输入示例：height = [0,1,0,2,1,0,1,3,2,1]
输出示例：6

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

核心思想与思路

核心思想

当前格子能接的水量 = min(左边最高柱子高度，右边最高柱子高度) - 当前柱子高度。只有当这个最小值大于当前柱子高度时，才能接到水。

双指针优化思路

为避免暴力法 O(n²) 的时间复杂度，使用双指针 + 维护左右最大高度的方式，将时间复杂度优化到 O(n)，空间复杂度 O(1)：

• 定义两个指针left和right，分别从数组两端向中间移动
• 维护left_max：left指针走过的所有柱子中的最大高度
• 维护right_max：right指针走过的所有柱子中的最大高度
• 谁小处理谁：
  • 如果left_max < right_max：说明当前left位置的接水量由left_max决定，计算后left右移
  • 如果right_max <= left_max：说明当前right位置的接水量由right_max决定，计算后right左移

直观理解

可以想象成：

• 左右两边都有“墙”（left_max和right_max）
• 哪边的墙更矮，水就会从哪边“漏”出去，所以当前位置的接水量由更矮的那面墙决定
• 每次移动指针时，都更新对应方向的最大高度

代码实现（Python）

from typing import List class Solution: def trap(self, height: List[int]) -> int: if not height: return 0 left = 0 right = len(height) - 1 left_max = 0 # 记录左边走过的最高柱子 right_max = 0 # 记录右边走过的最高柱子 ans = 0 # 总接水量 while left < right: # 更新左右最大高度 left_max = max(left_max, height[left]) right_max = max(right_max, height[right]) if left_max < right_max: # 左边最高 < 右边最高 → 当前left位置的接水量由left_max决定 ans += left_max - height[left] left += 1 else: # 右边最高 ≤ 左边最高 → 当前right位置的接水量由right_max决定 ans += right_max - height[right] right -= 1 return ans

关键知识点讲解

双指针技巧（Two Pointers）

适用场景：

• 数组/字符串需要从两端向中间遍历
• 需要在 O(n) 时间、O(1) 空间内解决问题
• 问题满足“哪边小/大就移动哪边”的决策逻辑

核心优势：

• 避免了暴力法的重复计算
• 不需要额外空间存储预处理的最大/最小值数组
• 逻辑清晰，代码简洁

与本题的结合：接雨水问题中，暴力法需要对每个位置分别找左、右最大值，时间 O(n²)；而双指针通过一次遍历，同时维护左右最大值，将时间优化到 O(n)，空间 O(1)。

单调栈解法（拓展知识点）

除了双指针，还有一种经典解法：单调栈，时间复杂度同样 O(n)，空间 O(n)。

核心思想：

• 维护一个单调递减栈，栈中存储柱子的索引
• 当遇到一个比栈顶元素高的柱子时，说明形成了“凹槽”，可以计算接水量
• 弹出栈顶作为“凹槽底部”，新栈顶作为“左边界”，当前柱子作为“右边界”

适用场景：

• 寻找“下一个更大/更小元素”
• 处理“凹槽”类问题（如接雨水、柱状图中最大矩形）

与双指针的对比：

动态规划预处理（基础思路）

这是理解双指针解法的前置基础，也是最容易想到的思路：

1. 预处理左最大数组：left_max[i]表示i位置左边（包括i）的最大高度
2. 预处理右最大数组：right_max[i]表示i位置右边（包括i）的最大高度
3. 遍历每个位置，接水量 =min(left_max[i], right_max[i]) - height[i]，累加得到结果

代码示例：

def trap_dp(height: List[int]) -> int: if not height: return 0 n = len(height) 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]) ans = 0 for i in range(n): ans += min(left_max[i], right_max[i]) - height[i] return ans

优缺点：

• ✅ 思路直观，容易理解
• ❌ 需要 O(n) 额外空间存储两个最大数组
• 双指针解法正是在此基础上，将空间优化到 O(1)

总结与思考

1. 接雨水问题的本质：每个位置的接水量由左右两侧更矮的墙决定
2. 解法演进：
   • 暴力法：O(n²) → 超时
   • 动态规划预处理：O(n) 时间，O(n) 空间 → 可接受
   • 双指针：O(n) 时间，O(1) 空间 → 最优解
   • 单调栈：O(n) 时间，O(n) 空间 → 另一种经典思路
3. 双指针的通用性：这种“两端向中间、根据条件移动指针”的思路，在很多数组问题中都有应用，比如：
   • 两数之和 II（输入有序数组）
   • 盛最多水的容器
   • 反转字符串

示例运行

以输入[0,1,0,2,1,0,1,3,2,1]为例：

1. 初始化left=0,right=9,left_max=0,right_max=0,ans=0
2. 逐步移动指针，计算每个位置的接水量
3. 最终累加得到ans=6，与题目输出一致