# LeetCode: 407. 接雨水II¶

## 1、题目描述¶

mn 都是小于110的整数。每一个单位的高度都大于 0 且小于 20000

给出如下 3x6 的高度图:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]



## 2、解题思路¶

• 围栏法

import heapq

class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
if not heightMap:
return 0
row, col = len(heightMap), len(heightMap[0])
ans = 0
heap = []
visited = [[0 for _ in range(col)] for _ in range(row)]

# 上下左右-坐标
surround = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 坐标验证
def available(m, n):
return 0 <= m < row and 0 <= n < col

for i in range(row):
heap.append([heightMap[i][0], i, 0])
heap.append([heightMap[i][col - 1], i, col - 1])
visited[i][0] = 1
visited[i][col - 1] = 1

for j in range(1, col - 1):
heap.append([heightMap[0][j], 0, j])
heap.append([heightMap[row - 1][j], row - 1, j])
visited[0][j] = 1
visited[row - 1][j] = 1

heapq.heapify(heap)

while heap:
height, x, y = heapq.heappop(heap)
for dx, dy in surround:
nx, ny = x + dx, y + dy
if available(nx, ny) and not visited[nx][ny]:
cur = [max(height, heightMap[nx][ny]), nx, ny]
ans += max(0, cur[0] - heightMap[nx][ny])
heapq.heappush(heap, cur)
visited[nx][ny] = 1
return ans