难度: Hard
给你一个 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.lengthn == heightMap[i].length1 <= m, n <= 2000 <= heightMap[i][j] <= 2 * 104运行时间: 126 ms
内存: 18.5 MB
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
m,n = len(heightMap),len(heightMap[0])
min_height = []
water = [[-1 for j in range(n)] for i in range(m)]
# top&low
for j in range(n):
heapq.heappush(min_height,(heightMap[0][j],0,j))
water[0][j] = heightMap[0][j]
heapq.heappush(min_height,(heightMap[m-1][j],m-1,j))
water[m-1][j] = heightMap[m-1][j]
# lf&rt
for i in range(1,m-1):
heapq.heappush(min_height,(heightMap[i][0],i,0))
water[i][0] = heightMap[i][0]
heapq.heappush(min_height,(heightMap[i][n-1],i,n-1))
water[i][n-1] = heightMap[i][n-1]
self.ans = 0
def cal_water(h,i,j):
if heightMap[i][j] >= h:
water[i][j] = heightMap[i][j]
else:
self.ans += h - heightMap[i][j]
water[i][j] = h
heapq.heappush(min_height, (water[i][j],i,j))
while min_height:
h, i, j = heapq.heappop(min_height)
if i > 0 and water[i-1][j] == -1:
cal_water(h,i-1,j)
if i < m-1 and water[i+1][j] == -1:
cal_water(h,i+1,j)
if j > 0 and water[i][j-1] == -1:
cal_water(h,i,j-1)
if j < n-1 and water[i][j+1] == -1:
cal_water(h,i,j+1)
return self.ans
该题解使用了最小堆来解决接雨水问题。首先将矩阵周边的元素加入最小堆，并初始化水位数组water。然后不断从堆顶取出高度最小的元素，判断其四周是否有未访问过的元素，如果有就计算该位置能接的雨水量，并将其加入最小堆。重复这个过程直到堆为空，最终的接雨水总量就是答案。
时间复杂度: O(mn * log(mn))
空间复杂度: O(mn)
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
m,n = len(heightMap),len(heightMap[0])
min_height = []
water = [[-1 for j in range(n)] for i in range(m)] # 初始化water数组，-1表示未访问过
# 将矩阵上下边界加入最小堆
for j in range(n):
heapq.heappush(min_height,(heightMap[0][j],0,j))
water[0][j] = heightMap[0][j]
heapq.heappush(min_height,(heightMap[m-1][j],m-1,j))
water[m-1][j] = heightMap[m-1][j]
# 将矩阵左右边界加入最小堆
for i in range(1,m-1):
heapq.heappush(min_height,(heightMap[i][0],i,0))
water[i][0] = heightMap[i][0]
heapq.heappush(min_height,(heightMap[i][n-1],i,n-1))
water[i][n-1] = heightMap[i][n-1]
self.ans = 0
# 计算位置(i,j)能接的雨水量
def cal_water(h,i,j):
if heightMap[i][j] >= h:
water[i][j] = heightMap[i][j]
else:
self.ans += h - heightMap[i][j] # 累加接雨水量
water[i][j] = h
heapq.heappush(min_height, (water[i][j],i,j))
while min_height:
h, i, j = heapq.heappop(min_height) # 取出堆顶元素
# 判断四周是否有未访问过的元素
if i > 0 and water[i-1][j] == -1:
cal_water(h,i-1,j)
if i < m-1 and water[i+1][j] == -1:
cal_water(h,i+1,j)
if j > 0 and water[i][j-1] == -1:
cal_water(h,i,j-1)
if j < n-1 and water[i][j+1] == -1:
cal_water(h,i,j+1)
return self.ans
在解决接雨水的问题时，水位的最高可能性始于边缘，因为边缘没有其他阻挡可以阻止水流走。通过从边界开始，我们可以确保我们模拟的水流是从最低点开始，逐渐向内部蔓延。这种方法可以避免不必要的计算，并能更准确地反映水的流动和积累。此外，边界元素是确定水能到达的最低高度的关键，它们自然形成了问题的'围栏'。
计算接雨水量时，需要考虑由于四周较高的障碍物可能造成的水位提升。如果仅使用原始矩阵中的高度，我们无法考虑到因周围更高的障碍物而在较低地方积累的水。水位数组中的水位代表了实际的水面高度，包括由于四周的堵塞而可能上升的水位。这种方法确保了每个位置的计算都基于最真实的水面情况，从而准确地模拟和计算积水量。
选择只更新未访问过的元素是为了优化算法的性能并避免重复计算。一旦一个元素的水位被计算并更新，就意味着它已经被考虑过，其水位是当前可能的最小水位。如果重新更新已访问过的元素，可能会导致不必要的重复计算和错误的水位计算。此外，使用最小堆的性质保证了我们总是从最低可能的水位开始扩散，确保整个计算过程的正确性和效率。