当前位置：首页 > news >正文

LeetCode 42 接雨水：python3 题解

news 2026/5/12 8:26:29

1. 问题核心理解
2. 解法详解
- 方法一：动态规划（预处理数组）
- 方法二：双指针法（最优解）⭐
- 方法三：单调栈（按层计算）
3. 完整代码实现（Python 3）
4. 算法复杂度对比总结
5. 常见疑问解答

1. 问题核心理解

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

直观理解：
想象一下，雨水会落在柱子之间的凹陷处。对于任意一个位置 i，它能存多少水，取决于它左边最高的柱子和右边最高的柱子。

水往低处流，所以水位高度不能超过左右两侧最高柱子中较矮的那个（木桶效应）。
当前位置能接的水量 = min(左边最高，右边最高) - 当前位置高度。
如果计算结果为负数，说明当前位置比边界高，接不到水，记为 0。

核心公式：

\[\text{water}[i] = \max(0, \min(\text{left_max}[i], \text{right_max}[i]) - \text{height}[i]) \]

下面我将详细讲解三种主流解法：动态规划、双指针（最优解）、单调栈。

2. 解法详解

方法一：动态规划（预处理数组）

思路：
核心公式需要知道每个位置左右的最大值。暴力法是每次遍历都重新扫描左右，效率低。动态规划的核心思想是空间换时间：

创建两个数组 left_max 和 right_max。
left_max[i] 存储位置 i 及其左边的最高柱子高度。
right_max[i] 存储位置 i 及其右边的最高柱子高度。
最后遍历一次数组，利用公式累加雨水量。

优点：逻辑最直观，容易理解。
缺点：需要 O(n) 的额外空间存储两个数组。

方法二：双指针法（最优解）⭐

思路：
动态规划中，我们发现其实不需要存储整个数组。我们可以用两个指针 left 和 right 分别从两端向中间移动。

维护两个变量 left_max 和 right_max，分别表示当前位置左边和右边已遇到的最大高度。
关键逻辑：比较 left_max 和 right_max。
- 如果 left_max < right_max：说明左边是短板。对于 left 位置来说，右边肯定有一个比 left_max 更高的柱子（即当前的 right_max），所以 left 位置的水位由 left_max 决定。计算完后，left 指针右移。
- 如果 left_max >= right_max：说明右边是短板。对于 right 位置来说，左边肯定有一个比 right_max 更高的柱子，所以 right 位置的水位由 right_max 决定。计算完后，right 指针左移。
这样可以在一次遍历中完成计算，且不需要额外数组。

优点：时间复杂度 O(n)，空间复杂度 O(1)，性能最优。
缺点：逻辑稍绕，需要理解“短板决定水位”的动态过程。

方法三：单调栈（按层计算）

思路：
前两种方法是按“列”计算（竖着算每一列能接多少水），单调栈是按“层”计算（横着算每一层凹槽能接多少水）。

维护一个单调递减栈，栈中存储柱子的索引。
遍历柱子，当当前柱子高度 h 大于栈顶柱子高度时，说明形成了一个凹槽（栈顶是底部，新栈顶是左边界，当前柱子是右边界）。
弹出栈顶作为底部，计算这一层凹槽的面积：宽度 × (左右边界最小高度 - 底部高度)。
重复直到栈满足单调递减，然后将当前柱子入栈。

优点：适合处理类似“寻找最近的大于/小于元素”的问题，思路独特。
缺点：代码逻辑相对复杂，空间复杂度 O(n)。

3. 完整代码实现（Python 3）

以下代码包含了上述三种解法。主函数 trap 使用了最优的双指针法。为了方便学习，我也添加了 trap_dp（动态规划）和 trap_stack（单调栈）方法。

from typing import Listclass Solution:def trap(self, height: List[int]) -> int:"""主解法：双指针法 (Two Pointers)时间复杂度：O(n)空间复杂度：O(1)这是面试中最推荐的解法，因为它在时间和空间上都是最优的。"""# 边界条件：如果柱子数量小于 3，无法形成凹槽接水if not height or len(height) < 3:return 0# 初始化左右指针，分别指向数组的头和尾left, right = 0, len(height) - 1# 初始化左右两侧遇到的最大高度left_max, right_max = 0, 0# 初始化总接水量water = 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 决定# 因为右边至少有一个 right_max 比 left_max 高，水不会漏出去water += left_max - height[left]left += 1  # 左指针向右移动else:# 右边较短，说明 right 位置的水位由 right_max 决定# 因为左边至少有一个 left_max 比 right_max 高water += right_max - height[right]right -= 1  # 右指针向左移动return waterdef trap_dp(self, height: List[int]) -> int:"""解法二：动态规划 (Dynamic Programming)时间复杂度：O(n)空间复杂度：O(n)思路：预先计算每个位置左边和右边的最大高度，存储在数组中。"""if not height or len(height) < 3:return 0n = len(height)# left_max[i] 表示位置 i 左边（包括 i）的最高柱子高度left_max = [0] * n# right_max[i] 表示位置 i 右边（包括 i）的最高柱子高度right_max = [0] * n# 1. 从左向右遍历，填充 left_max 数组left_max[0] = height[0]for i in range(1, n):left_max[i] = max(left_max[i-1], height[i])# 2. 从右向左遍历，填充 right_max 数组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])# 3. 遍历每个位置，计算接水量并累加water = 0for i in range(n):# 当前位置水位 = min(左边最高，右边最高) - 当前高度water += min(left_max[i], right_max[i]) - height[i]return waterdef trap_stack(self, height: List[int]) -> int:"""解法三：单调栈 (Monotonic Stack)时间复杂度：O(n)空间复杂度：O(n)思路：按层计算雨水。维护一个递减栈，遇到比栈顶高的柱子时，说明形成了凹槽。"""if not height or len(height) < 3:return 0stack = []  # 栈中存储柱子的索引，保持对应的高度单调递减water = 0for i, h in enumerate(height):# 当当前柱子高度大于栈顶柱子高度时，说明可能形成凹槽while stack and h > height[stack[-1]]:# 弹出栈顶元素，作为凹槽的底部bottom = stack.pop()# 如果栈为空，说明没有左边界，无法形成凹槽，跳出循环if not stack:break# 新的栈顶元素作为左边界left = stack[-1]# 计算凹槽的宽度：当前索引 - 左边界索引 - 1width = i - left - 1# 计算凹槽的高度：min(左边界高度，右边界高度) - 底部高度bounded_height = min(height[left], h) - height[bottom]# 累加这一层的雨水量water += width * bounded_height# 将当前柱子索引入栈stack.append(i)return water# --- 测试代码 ---
if __name__ == "__main__":sol = Solution()# 测试用例test_height = [0,1,0,2,1,0,1,3,2,1,2,1]print(f"输入高度图：{test_height}")print(f"双指针法结果：{sol.trap(test_height)}")       # 期望输出：6print(f"动态规划法结果：{sol.trap_dp(test_height)}")   # 期望输出：6print(f"单调栈法结果：{sol.trap_stack(test_height)}")  # 期望输出：6

4. 算法复杂度对比总结

解法	时间复杂度	空间复杂度	适用场景	推荐度
动态规划	O(n)	O(n)	逻辑简单，容易编写，适合初学者理解原理	⭐⭐⭐⭐
双指针	O(n)	O(1)	空间最优，面试标准答案，性能最好	⭐⭐⭐⭐⭐
单调栈	O(n)	O(n)	适合处理横向凹槽问题，思路独特	⭐⭐⭐

5. 常见疑问解答

Q1: 双指针法中，为什么 left_max < right_max 时可以直接计算 left 处的水量？

答：因为 right_max 代表的是 right 指针及其右侧遇到的最大值。既然 left_max < right_max，说明在 left 的右侧一定存在一个高度至少为 right_max 的柱子。对于 left 位置来说，它左边的最高是 left_max，右边的最高至少是 right_max。根据木桶效应，水位高度取决于较小值，也就是 left_max。所以此时 left 处的水量是确定的，可以放心计算并移动指针。