目录

0407:接雨水 II(★★)

力扣第 407 题

题目

给你一个 m x n 的矩阵,其中的值均为非负整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。

示例 1:

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后,雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例 2:

输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10

提示:

  • m == heightMap.length
  • n == heightMap[i].length
  • 1 <= m, n <= 200
  • 0 <= heightMap[i][j] <= 2 * 104

相似问题:

分析

#1

  • 可以将下雨看作动态的过程,假如下到高度 h 时,某个柱子上的雨水能流出去,该柱子能接的最大高度即是 h
  • 雨水能否流出去是一个连通性问题,因此可以考虑用并查集
  • 从低到高遍历所有柱子,维护连通性,高度 h 时与边界连通的即加到结果中
    • 可以通过边界所在连通块的大小变化计算
  • 最后再减去柱子本身的高度即可
 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
class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        def find(x):
            if f[x]!=x:
                f[x]=find(f[x])
            return f[x]
        
        def union(x,y):
            fx,fy = find(x),find(y)
            if fx!=fy:
                f[fx]=fy
                sz[fy]+=sz[fx]

        H = heightMap
        m,n = len(H),len(H[0])
        f = list(range(m*n+1))
        sz = [1]*(m*n+1)
        d = defaultdict(list)
        for i,j in product(range(m),range(n)):
            d[H[i][j]].append((i,j))
        res,pre=0,1
        for h in sorted(d):
            for i,j in d[h]:
                if i in [0,m-1] or j in [0,n-1]:
                    union(i*n+j,m*n)
                for x,y in [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]:
                    if 0<=x<m and 0<=y<n and H[x][y]<=h:
                        union(i*n+j,x*n+y)
            cur = sz[find(m*n)]
            res += (cur-pre)*h-len(d[h])*h
            pre = cur
        return res

272 ms

#2

  • 还可以借鉴 0042 的双指针思想,从外到内遍历
  • 对于最外圈,先找到最低柱子 a
    • 则对于 a 相邻的柱子 b,能接到的雨水即是 max(0,a-b)
  • 然后将 a 替换为 b,形成新的外圈,并更新 b 的高度为 max(a,b)
  • 逐步缩小外圈即可得到每个位置能接到的雨水
  • 每轮要找外圈里的最低柱子,用堆维护即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        H = heightMap
        m,n = len(H),len(H[0])
        pq = []
        for i, j in product(range(m), range(n)):
            if i in [0, m-1] or j in [0, n-1]:
                heappush(pq, (H[i][j], i, j))
                H[i][j] = -1
        res = 0
        while pq:
            h,i,j = heappop(pq)
            for x, y in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
                if 0<=x<m and 0<=y<n and H[x][y]!=-1:
                    res += max(0,h-H[x][y])
                    heappush(pq, (max(h,H[x][y]),x,y))
                    H[x][y] = -1
        return res

168 ms