XTY的小站
记录技术笔记和技术博客

42. Trapping Rain Water

26 Jun 2024

42. Trapping Rain Water (Medium) 接雨水

题干

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5] Output: 9

Constraints:

思路

我的思路

数组元素非负，需要找到三个或多余三个的子数组，头和尾的元素大于所有其他的元素。将中间元素和头尾之间较小元素的差值累加。

实现：

思路有问题：

  • 拆解成子问题，不能拆成不确定的。子问题拆成一个U型的子数组并没有降低复杂度，应该拆成的是独立的每根柱子

正确思路：暴力解法

每根柱子能接到的雨水，受其左区间和右区间的最高值决定。

所以只要循环每个柱子，找到每个柱子左右的最高值即可。

class Solution:
    def trap(self, height: List[int]) -> int:
        trap_water = 0

        if len(height) < 2:
            return trap_water

        left_max= height[0]
        right_max = max(height[1:])

        for i in range(1, len(height)-1):
            trap_limit = min(left_max, right_max)
            if height[i] < trap_limit:
                trap_water += trap_limit - height[i]
            left_max = max(left_max, height[i])
            right_max = max(height[i+1:])
        
        return trap_water

优化解法（备忘录）

暴力解法中，寻找左最大值的时间是O(1)，但是因为循环右边最大值把时间从O(n)增长为O(n^2)。转换思路，可以把左最大值和右最大值分开寻找，一次从左向右，一次从右向左，这样只需要使用一个备忘数据结构，即可将时间复杂度将为O(n)。当然，代价是空间复杂度增长为O(n).

算法本质没有变，还是暴力解法

class Solution:
    def trap(self, height: List[int]) -> int:
        water_trapped = 0

        if len(height) < 3:
            return water_trapped

        left_max_heights = [ 0 for x in range(len(height)) ]

        left_max = 0
        for i in range(1, len(height)):
            left_max = max(height[i-1], left_max)
            left_max_heights[i] = left_max
        right_max = 0
        for j in range(len(height)-2, 0, -1):
            right_max = max(height[j+1], right_max)
            limit = min(left_max_heights[j], right_max)
            if height[j] < limit:
                water_trapped += limit - height[j]
        
        return water_trapped

双指针解法

上面的备忘录解法使用了空间复杂度O(n)，先通过循环（从左到右从右到左两次循环）把所有节点的左最大值和右最大值都找到了才计算。

那么是否可以左右同时循环（双指针），并且边循环边计算呢（节省空间）？

很容易会想到这里的问题的关键是找到左右指针的移动策略。

首先可以通过左右指针分别开始发现left_max和right_max，当然，这里是[0,left]的left_max，是[right,len(height)]的right_max，并不是任意元素i的[0,i]到[i,len(height)]的left_max和right_max。

那这样可以吗？其实是可以的，因为我们关心的其实是两个最大值中的最小值，如果确定一边的最大值，并且比另外一边的任意一个值小，就可以算出来当前柱子的雨量了。

想通了这点，其实就想通了这个算法了

class Solution:
    def trap(self, height: List[int]) -> int:
        water_trapped = 0

        if len(height) < 3:
            return water_trapped
        
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        while left < right:
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])
            
            if left_max < right_max:
                water_trapped += left_max - height[left]
                left += 1
            else:
                water_trapped += right_max - height[right]
                right -= 1
        
        return water_trapped

单调栈解法

可以使用单调栈的思路

class Solution:
    def trap(self, height: List[int]) -> int:
        water_trapped = 0

        if len(height) < 3:
            return water_trapped
        
        st: List = []

        for i in range(len(height)):
            while st and height[i] > height[st[-1]]:
                st_popped = st.pop()
                # 若弹出当前元素后，单调栈为空，说明左边没有比它大的元素
                if not st:
                    break
                water_trapped += (min(height[i], height[st[-1]]) - height[st_popped]) * (i - st[-1] - 1)
            st.append(i)
        return water_trapped