LeetCode07：接雨水

7.接雨水

题目

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

image-20240615192506854

题解

（1）动态规划法

动态规划（Dynamic Programming, DP）是一种算法设计技巧，它将一个复杂的问题分解为更小的子问题，并存储这些子问题的解，以避免重复计算。这种方法特别适用于具有以下两个特性的问题：

  1. 重叠子问题：问题可以分解为多个子问题，这些子问题会重复出现多次。
  2. 最优子结构：问题的最优解包含其子问题的最优解。

思路

  1. 对于下标i，雨水能达到的最大高度是i两边的最大高度的最小值。
  2. 对于下标i，雨水量是能达到的最大高度减去i处的柱子高度height[i]
  • 如何计算两边的最大高度呢？

朴素的做法是：对于每一个位置，分别向左和向右扫描，记录左右两边的最大高度。

时间复杂度：O($n^2$)

动态规划法：如果已知每个位置两边的最大高度，就可以在O(n)的时间得出结果。

时间复杂度：O(n)

  • 如何计算每个位置两边的最大高度呢

创建2个长度为n的数组leftMax和rightMax。leftMax[i]表示下标i及其左边位置的最大高度，rightMax[i]表示下标i及其右边位置的最大高度。

显然，两端的元素已经确定。leftMax[0] = height[0]，rightMax[n-1]=height[n-1]

其他元素的计算方式：正向遍历数组height得到leftMax，反向遍历数组height得到rightMax。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def trap(self, height):
        if not height:
            return 0
        
        n = len(height)
        
        leftMax = [height[0]] + [0] * (n-1)
        for i in range(1,n):
            leftMax[i] = max(leftMax[i-1],height[i])
            
        rightMax = [0] * (n-1) + [height[n-1]]
        for i in range(n-2,-1,-1):
            rightMax[i] = max(rightMax[i+1],height[i])
        
        ans = sum(min(leftMax[i],rightMax[i])-height[i] for i in range(n))
        return ans

（2）单调栈

维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height中的元素递减。

从左到右遍历height数组，遍历到下标i的时候，如果栈内至少有2个元素，栈顶为top，top下面是left，则一定有height[top]<=height[left]。如果height[i] > height[top]，则可以接到雨水。

雨水的宽度：i - left -1

雨水的高度：min(height[left],height[i]) - height[top]

循环条件

为了得到left，需要将top出栈，对top计算能接到的雨水量后，left就变成了新的top，如此重复操作，直到栈为空或者栈顶对应的元素大于或等于height[i]。完成对top和i的计算后，将i入栈，继续遍历。

时间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def trap(self, height):
        ans = 0
        stack = list()
        n = len(height)
        
        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]:
                top = stack.pop()
                if not stack:
                    break
                left = stack[-1]
                currWidth = i - left - 1
                currHeight = min(height[left], height[i]) - height[top]
                ans += currWidth * currHeight
            stack.append(i)
        
        return ans

（3） 双指针

在动态规划中，需要维护两个数组leftMax和rightMax，因此空间复杂度是O(n)。使用双指针和双变量可以代替两个数组，使得空间复杂度是O(1)。

初始值：指针left=0，指针right=len(height)-1,两个变量leftMax=0,rightMax=0

下标i能接的雨水量由leftMax[i]和rightMax[i]的最小值决定。

指针left只能右移，指针right只能左移，移动指针过程中需要维护两个变量leftMax和rightMax的值。

当两个指针没有相遇时：（while left < right）

image-20240617172305647

时间复杂度：O(n)，其中 n是数组的长度，两个指针的移动总次数不超过 n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def trap(self, height):
        ans = 0
        left, right = 0, len(height) - 1
        leftMax = rightMax = 0

        while left < right:
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            if height[left] < height[right]:
                ans += leftMax - height[left]
                left += 1
            else:
                ans += rightMax - height[right]
                right -= 1
        
        return ans