LeetCode 42 接雨水：python3 题解

碛物 · 5 小时前

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

1. 问题核心理解

题目描述：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
直观理解：
想象一下，雨水会落在柱子之间的凹陷处。对于任意一个位置 i，它能存多少水，取决于它左边最高的柱子和右边最高的柱子。

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

核心公式：

\[\text{water} = \max(0, \min(\text{left_max}, \text{right_max}) - \text{height})\]
下面我将详细讲解三种主流解法：动态规划、双指针（最优解）、单调栈。
2. 解法详解

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

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

创建两个数组 left_max 和 right_max。

left_max 存储位置 i 及其左边的最高柱子高度。

right_max 存储位置 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 List
class 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 water
def trap_dp(self, height: List[int]) -> int:
      """
      解法二：动态规划 (Dynamic Programming)
      时间复杂度：O(n)
      空间复杂度：O(n)
      思路：预先计算每个位置左边和右边的最大高度，存储在数组中。
      """
      if not height or len(height) < 3:
         return 0

      n = 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 = 0
      for i in range(n):
         # 当前位置水位 = min(左边最高，右边最高) - 当前高度
         water += min(left_max[i], right_max[i]) - height[i]

      return water
def trap_stack(self, height: List[int]) -> int:
      """
      解法三：单调栈 (Monotonic Stack)
      时间复杂度：O(n)
      空间复杂度：O(n)
      思路：按层计算雨水。维护一个递减栈，遇到比栈顶高的柱子时，说明形成了凹槽。
      """
      if not height or len(height) < 3:
         return 0

      stack = []  # 栈中存储柱子的索引，保持对应的高度单调递减
      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]

            # 计算凹槽的宽度：当前索引 - 左边界索引 - 1
            width = 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)}")    # 期望输出：6
print(f"动态规划法结果：{sol.trap_dp(test_height)}") # 期望输出：6
print(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 处的水量是确定的，可以放心计算并移动指针。

Q2: 单调栈中 width = i - left - 1 是怎么来的？

答：i 是当前右边界索引，left 是弹出底部后新的栈顶（左边界）索引。凹槽的宽度是左右边界之间的距离，不包含边界本身，所以是 i - left - 1。例如左边界在索引 1，右边界在索引 4，中间能接水的柱子索引是 2 和 3，宽度为 2，即 4 - 1 - 1 = 2。

Q3: 为什么数组长度小于 3 时直接返回 0？

答：接雨水至少需要三根柱子才能形成一个凹槽（左边界、底部、右边界）。如果只有 1 根或 2 根柱子，水会直接流走，无法储存。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册

LeetCode 42 接雨水：python3 题解

相关帖子

签约作者

LeetCode 42 接雨水：python3 题解

相关帖子

相关推荐

签约作者