接雨水

发表于 更新于

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

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

示例:

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

思路

思路一:

结合数据和图,可以看出能够存积水的位置 i ,始终满足条件:

  1. height[i] < height[i-n]
  2. height[i] < height[i+m]

其中 m,n 均大于 0,同时判定两个条件会很麻烦,我们试着先找出所有高度中最高的,以这个最高的将这个高度数组分为左右两边,然后依次从 left 遍历到最高的,从 right 遍历到最高的,遍历过程中,只需要找出局部最高 part_max,
局部最高与其余高度值的差值和即为积水和

以给的例子为例,[0,1,0,2,1,0,1,3,2,1,2,1]:

  1. max_height = 3. 所在索引为 7
  2. 以左边为例,从左到最高的数组为 [0,1,0,2,1,0,1], 对于的局部最高的数组为 [0,1,1,2,2,2,2]
  3. 高度差依次为:[0,0,1,0,1,2,1]
  4. 则左边积水和为 5
  5. 同理可求右边为 1
  6. 则最终结果为 6

思路二:

双指针:假设数组 height, 长度为 n, left_max = right_max = 0, 面积为 area = 0 ,两个指针left,right 初始分别位于 0, n - 1 的位置

  1. height[left] < height[right], 有解法一中可以知道,这个时候只要找到 left_max > height[left] 就可以积水了,所以有: 
             1.  如果 height[left] > left_max: left_max = height[left]
         2.  否则 area += left_max - height[left]
         3.  left += 1
  2. height[left] >height[right]:
    1. 如果 height[right] > right_max: right_max = height[right]
    2. 否则 area += right_max - height[right]
    3. right -= 1

解法

解法一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def trap(self, height: List[int]) -> int:
        
        height_len = len(height)
        
        if height_len < 3:
            return 0
        
        max_value = 0
        max_index = 0
        for key,value in enumerate(height):
            if value > max_value:
                max_value = value
                max_index = key
        
        # 面积      
        area = 0
  
        # left -> max
        part_max = height[0]
        for left in range(max_index):
            if height[left] > part_max:
                part_max = height[left]
            else:
                area += part_max - height[left]
        # right -> max
        part_max = height[height_len-1]
        for right in range(height_len-1,max_index,-1):
            if height[right] > part_max:
                part_max = height[right]
            else:
                area += part_max - height[right]
        
        return area

解法二

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:
        height_len = len(height)
        if height_len < 3:
            return 0
        left_max = right_max = 0
        left,right = 0, height_len - 1
        area = 0
        
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    area += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    area += right_max - height[right]
                right -= 1
        return area