-
Notifications
You must be signed in to change notification settings - Fork 160
/
407.py
16 lines (16 loc) · 781 Bytes
/
407.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def trapRainWater(self, heightMap):
m, n, heap, trapped = len(heightMap), len(heightMap and heightMap[0]), [], 0
for i in range(m):
for j in range(n):
if i in {0, m - 1} or j in {0, n - 1}:
heapq.heappush(heap, (heightMap[i][j], i, j))
heightMap[i][j] = -1
while heap:
h, i, j = heapq.heappop(heap)
for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 < x < m - 1 and 0 < y < n - 1 and heightMap[x][y] != -1:
trapped += max(h - heightMap[x][y], 0)
heapq.heappush(heap, (max(heightMap[x][y], h), x, y))
heightMap[x][y] = -1
return trapped