1.题目基本信息

1.1.题目描述

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

1.2.题目地址

https://leetcode.cn/problems/trapping-rain-water-ii/description/

2.解题方法

2.1.解题思路

最小堆

时间复杂度：O(mnlog(mn))

2.2.解题步骤

第一步，构建矩阵最外围的最小堆，每一项的形式为(height,row,col)，记为heap；同时将入堆的元素标记为已访问（设置为-1）

第二步，持续从heap中弹出元素，直到为空

• 2.1.对弹出的节点(h,r,c)，遍历该位置周围没有访问过的位置

• 2.2.如果该位置节点的height小于h，则填上h-height的高度；反之，不填；将填入的高度求和到结果变量中；然后将该位置标记为已访问（设置为-1）

• 2.3.将填高后的节点进行入堆

3.解题代码

python代码

from heapq import heapify, heappush, heappop

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        # 思路：最小堆
        directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
        # 第一步，构建矩阵最外围的最小堆，每一项的形式为(height,row,col)，记为heap；同时将入堆的元素标记为已访问（设置为-1）
        m, n = len(heightMap), len(heightMap[0])
        heap = []
        for i in range(m):
            heappush(heap, (heightMap[i][0], i, 0))
            heappush(heap, (heightMap[i][n - 1], i, n - 1))
            heightMap[i][0] = -1
            heightMap[i][n - 1] = -1
        for j in range(n):
            heappush(heap, (heightMap[0][j], 0, j))
            heappush(heap, (heightMap[m - 1][j], m - 1, j))
            heightMap[0][j] = -1
            heightMap[m - 1][j] = -1
        # 第二步，持续从heap中弹出元素，直到为空
        result = 0
        while heap:
            # 2.1.对弹出的节点(h,r,c)，遍历该位置周围没有访问过的位置
            h, r, c = heappop(heap)
            for (dr, dc) in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and heightMap[nr][nc] != -1:
                    height = heightMap[nr][nc]
                    # 2.2.如果该位置节点的height小于h，则填上h-height的高度；反之，不填；将填入的高度求和到结果变量中；然后将该位置标记为已访问（设置为-1）
                    result += max(height, h) - height
                    heightMap[nr][nc] = -1
                    # 2.3.将填高后的节点进行入堆
                    heappush(heap, (max(height, h), nr, nc))
        return result

4.执行结果