Sui Xin's Blog

[LeetCode]42. 接雨水（Trapping Rain Water）

Posted on In Disqus:

题目描述

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


上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

  1. 解法一：暴力。对于每个位置，该位置能够接到的雨水量为其左边的最高墙与右边的最高墙的较小值减去该位置的墙高。时间复杂度 $O(n^2)$；
  2. 解法二：动态规划（推荐）。动态的存储每个位置的左边最高墙与右边最高墙。空间复杂度增加为 $O(n)$；
  3. 解法三：栈（难理解，不推荐）。可画图理解。使用栈来存储墙的索引。每次当前元素 t 大于栈顶元素时，可连续出栈，计算该元素与当前元素 t 的距离，使用该元素左边的元素与当前元素 t 的较小值作为边界，减去该元素的高度即为“该元素到当前元素 t 能够储存的雨水量”，该值可能为负，表示这个位置不能存储这些雨水，会与后面计算的抵消掉。

  4. 解法四：双指针（妙！）。使用双指针可一次性遍历左边界与右边界，使用 $O(n)$ 的时间复杂度与 $O(1)$ 的空间复杂度完成。

    1. 初始化 left 指针指向数组头，right 指针指向数组尾；

    2. 若 left < right，循环：

      1. 若 height[left] < height[right]，执行：
        1. 若 height[left] >= max_left：更新 max_left
        2. 否则结算当前节点的雨水量：max_left - height[left]
        3. left += 1
      2. 否则，执行：
        1. 若 height[right] >= max_right：更新 max_right
        2. 否则结算当前节点的雨水量：max_right - height[right]
        3. right -= 1

      这样做的理由是：每次交替更新的都是较小的那一个方向，因为较大的那个方向肯定能够满足，所以该位置的雨水量取决于较小的方向；而若该位置的值小于原来的边界，以原来的边界为准，否则说明该位置大于等于原边界，不会存储到雨水，更新原边界即可。

代码

Python 3.6

解法一：暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def trap(self, height: List[int]) -> int:
        length = len(height)
        if length < 3:
            return 0
        res = 0
        for i in range(length):
            max_left = height[i]
            for j in range(i - 1, -1, -1):
                max_left = max(height[j], max_left)
            if max_left <= height[i]:
                continue
            max_right = height[i]
            for j in range(i + 1, length):
                max_right = max(height[j], max_right)
            res += min(max_left, max_right) - height[i]
        return res

超出时间限制

解法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def trap(self, height: List[int]) -> int:
        length = len(height)
        if length < 3:
            return 0
        max_left, max_right = [], []
        for i in range(length):
            if max_left:
                max_left.append(max(max_left[-1], height[i]))
            else:
                max_left.append(height[i])
            if max_right:
                max_right.append(max(max_right[-1], height[length - 1 - i]))
            else:
                max_right.append(height[length - 1 - i])
        max_right.reverse()

        res = 0
        for i in range(length):
            res += min(max_left[i], max_right[i]) - height[i]
        return res

执行用时 : 92 ms
内存消耗 : 14.5 MB
注：用空间换时间，空间复杂度由解法一的 O(1) 变成了 O(n)。

解法三：栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def trap(self, height: List[int]) -> int:
        length = len(height)
        if length < 3:
            return 0
        stack = []
        res = 0
        for i in range(length):
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()
                if not stack:
                    break
                distance = i - stack[-1] - 1
                bounded_height = min(height[i], height[stack[-1]]) - height[top]
                res += distance * bounded_height
            stack.append(i)
        return res

执行用时 : 88 ms
内存消耗 : 14.6 MB

解法四：双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def trap(self, height: List[int]) -> int:
        length = len(height)
        if length < 3:
            return 0
        res = 0
        
        max_left, max_right = 0, 0
        left, right = 0, length - 1
        while left < right:
            if height[left] < height[right]:
                if height[left] >= max_left:
                    max_left = height[left]
                else:
                    res += max_left - height[left]
                left += 1
            else:
                if height[right] >= max_right:
                    max_right = height[right]
                else:
                    res += max_right - height[right]
                right -=1
        return res

执行用时 : 80 ms
内存消耗 : 14.4 MB

参考

https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/

Related Posts