LeetCode | 接雨水

题目#

给定一个非负整数数组 height，每个数字表示一个柱子的高度。

下雨之后，柱子之间可能会积水。求最多可以接多少水。

示例：

1
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
2
输出：6

讲解#

建议：先自己想一下“每个位置为什么能接水”，再看解析。否则双指针这一步会比较抽象。

这道题不要先想着“一整块水”怎么算，而是先看每一个位置能接多少水。

一个位置能接多少水，取决于它左右两边的挡板：

具体来说：

1
当前位置能接的水 = min(左边最高高度, 右边最高高度) - 当前高度

如果这个值小于 0，就说明这个位置接不了水。

比如某个位置高度是 1，它左边最高是 3，右边最高是 2，那么它最多只能接到高度 2，因为右边挡板更矮。

所以这个位置能接：

1
min(3, 2) - 1 = 1

暴力做法是：对每个位置，都向左找一次最高柱子，再向右找一次最高柱子，然后计算这个位置能接多少水。这样可以做出来，但是每个位置都要左右扫描，时间复杂度是 O(n^2)。

双指针的目标就是避免重复扫描。

我们让 left 从左往右走，right 从右往左走，同时维护：

1
left_max  = left 左侧已经见过的最高柱子
2
right_max = right 右侧已经见过的最高柱子

关键问题是：什么时候可以确定某个位置能接多少水？

当 height[left] < height[right] 时，可以先结算 left 这个位置。

原因是：右边此时至少有 height[right] 这根柱子，而且它比 height[left] 高。也就是说，left 右侧不是完全没有挡板，右边挡板已经够用了。

所以 left 位置能接多少水，主要取决于左边最高的柱子 left_max。

此时可以计算：

1
left_max - height[left]

然后让 left 往右移动。

反过来，当 height[left] >= height[right] 时，可以先结算 right 这个位置。

原因是：左边此时至少有 height[left] 这根柱子，而且它不低于 height[right]。所以 right 左侧挡板已经够用了。

此时 right 位置能接多少水，主要取决于右边最高的柱子 right_max。

此时可以计算：

1
right_max - height[right]

然后让 right 往左移动。

这就是双指针的核心：每次只结算“较矮的一边”。因为较矮的一边已经能确定自己的另一侧有挡板，不需要再等更远的位置。

代码#

1
from typing import List
2

3

4
class Solution:
5
    def trap(self, height: List[int]) -> int:
6
        ans = 0
7
        left = 0
8
        right = len(height) - 1
9
        left_max = 0
10
        right_max = 0
11

12
        while left < right:
13
            left_max = max(left_max, height[left])
14
            right_max = max(right_max, height[right])
15

16
            if height[left] < height[right]:
17
                ans += left_max - height[left]
18
                left += 1
19
            else:
20
                ans += right_max - height[right]
21
                right -= 1
22

23
        return ans

1
from src.python._042_Trapping_Rain_Water import Solution
2

3

4
sol = Solution()
5

6
assert sol.trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
7
assert sol.trap([4, 2, 0, 3, 2, 5]) == 9
8
assert sol.trap([1, 2, 3]) == 0
9
assert sol.trap([]) == 0
10

11
print("PASS")

参考资料#

• LeetCode 原题：https://leetcode.com/problems/trapping-rain-water/
• 力扣官方题解：https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/