42. 接雨水

Posted on Edited on In Views: Word count in article: 566 Reading time ≈ 1 mins.

42. 接雨水

题目链接：42. 接雨水

题目描述

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

核心思考：前后缀最值的应用

接雨水问题的核心在于：对于每一个位置 i，它能接多少水，取决于它左侧最高柱子和右侧最高柱子中的较短者。

每一个位置 i 能接的水量公式为：
$water[i] = \min(\text{max_left}[i], \text{max_right}[i]) - height[i]$

为了高效获取每个位置的左右最值，我们可以使用类似“前缀和”的思想，提前预处理出两个数组：

  1. 前缀最大值数组 (pre)：记录从左向右扫描到位置 i 时的最大高度。
  2. 后缀最大值数组 (suf)：记录从右向左扫描到位置 i 时的最大高度。

最后再次遍历数组，按照公式累加每个位置的储水量即可。这种方法将原本可能需要的 $O(n^2)$ 暴力计算优化到了 $O(n)$ 时间复杂度。

解题思路 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        pre = [0] * n
        suf = [0] * n
        pre[0] = height[0]
        suf[-1] = height[-1]

        for i in range(1,n):
            pre[i] = max(pre[i-1],height[i])
        for i in range(n-2,-1,-1):
            suf[i] = max(suf[i+1],height[i])
        
        ans = 0
        for i in range(n):
            ans += min(pre[i],suf[i]) - height[i]
        return ans

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 为数组长度。我们需要进行三次线性遍历（两次预处理，一次计算结果）。
  • 空间复杂度：$O(n)$。我们使用了 pre 和 suf 两个长度为 n 的额外数组来存储前后缀最大值。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

1
num1 num2 num3 ... numN

输入一行整数数组，以空格分隔。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys

class Solution:
    def trap(self, height: List[int]) -> int:
    n = len(height)
            pre = [0] * n
            suf = [0] * n
            pre[0] = height[0]
            suf[-1] = height[-1]

            for i in range(1,n):
                pre[i] = max(pre[i-1],height[i])
            for i in range(n-2,-1,-1):
                suf[i] = max(suf[i+1],height[i])

            ans = 0
            for i in range(n):
                ans += min(pre[i],suf[i]) - height[i]
            return ans

def main():
    nums = list(map(int, sys.stdin.read().strip().split()))

    sol = Solution()
    result = sol.trap(nums)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

1
echo "2 -1 3 4 -5" | python solution.py