接雨水

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

Leetcode 双指针动态规划

开始写作

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

尝试一

思路

对于第i个格子能装的水的高度取决于min(左边最高的柱子，右边最高的柱子) - 第i个格子的高度最朴素的写法就是双重循环遍历就行，但是提交会超时

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

尝试二

思路

尝试一中重复寻找最大值的行为是多余的，借鉴动态规划思路，可以建立两个数组以记录第i个数左右两边的最大值。时间复杂度只有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)-1):
            min_max = min(left_max[i], right_max[i])
            water = min_max - height[i]
            if water > 0:
                res += water
 
        return res

解法三

思路

第i处的接水量取决于LeftMax和RightMax两者中更小的数，将i看做两者中更短者，此时一定存在比i更高的，因此i处储水量一定是能求出来的。求完后，再移动i。

答案

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