接雨水

本文详细解析 LeetCode 42. 接雨水问题，从暴力解法到动态规划再到双指针优化，逐步展示算法优化过程。

Leetcode 双指针动态规划 Python

阅读要点

接雨水问题的核心公式：每个位置能接的水量 = min(左边最高柱子, 右边最高柱子) - 当前高度
暴力解法通过双重循环计算每个位置的左右最大高度，时间复杂度 O(n²)，会超时
动态规划解法通过预计算左右最大高度数组，将时间复杂度优化至 O(n)，空间复杂度 O(n)
双指针解法利用左右指针和两个变量实时维护左右最大高度，将空间复杂度优化至 O(1)

题目

https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked

尝试一：暴力解法

思路

对于第 i 个格子，它能接的水量取决于 min(左边最高的柱子, 右边最高的柱子) - height[i]。最直接的写法是双重循环：外层遍历每个位置，内层分别向左和向右寻找最大值。但这种方法时间复杂度为 O(n²)，提交会超时。

代码

class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        for i in range(len(height)):
            left_max, right_max = 0, 0
            for j in range(len(height)):
                if j < i:
                    left_max = max(height[j], left_max)
                elif j > i:
                    right_max = max(height[j], right_max)
            min_max = min(left_max, right_max)
            water_height = min_max - height[i]
            if water_height < 0:
                continue
            res += water_height
        return res

尝试二：动态规划

思路

暴力解法中重复寻找最大值是多余的。我们可以预先计算每个位置左边和右边的最大高度，存储在两个数组中。这样只需三次线性遍历：第一次从左到右计算 left_max，第二次从右到左计算 right_max，第三次遍历计算每个位置的储水量。时间复杂度 O(n)，空间复杂度 O(n)。

代码

class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        left_max = [0] * len(height)
        right_max = [0] * len(height)
        # 计算每个位置左边的最大高度
        for i in range(1, len(height) - 1):
            left_max[i] = max(left_max[i-1], height[i-1])
        # 计算每个位置右边的最大高度
        for i in range(len(height) - 2, -1, -1):
            right_max[i] = max(right_max[i+1], height[i+1])
        # 计算总储水量
        for i in range(len(height)):
            min_max = min(left_max[i], right_max[i])
            water = min_max - height[i]
            if water > 0:
                res += water
        return res

解法三：双指针优化

思路

观察动态规划解法，我们发现每个位置的储水量只取决于 leftMax 和 rightMax 中较小的那个。我们可以用两个指针 i 和 j 分别从左右向中间移动，同时维护 leftMax 和 rightMax。当 leftMax < rightMax 时，位置 i 的储水量由 leftMax 决定，计算后移动左指针；反之，位置 j 的储水量由 rightMax 决定，计算后移动右指针。这样只需一次遍历，空间复杂度降为 O(1)。

代码

class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        i, j = 1, len(height) - 2
        leftMax, rightMax = 0, 0
        while i <= j:
            leftMax = max(leftMax, height[i-1])
            rightMax = max(rightMax, height[j+1])
            if leftMax < rightMax:
                water = leftMax - height[i]
                if water > 0:
                    res += water
                i += 1
            else:
                water = rightMax - height[j]
                if water > 0:
                    res += water
                j -= 1
        return res