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)

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 的额外数组来存储前后缀最大值。