2021-07-15：接雨水 II。给你一个 m x n 的矩阵，其中的值均为非负整（mxn）

# 行业要闻 2024-04-11 21:17 来源：文通网

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

福大大答案2021-07-15：

小根堆是否访问矩阵。思路跟昨天的每日一题差不多，但代码相对复杂。昨天的每日一题，是两端的柱子逐步向中间移动，收集到的雨水就是答案。今天的每日一题，是一圈的柱子逐个向中间移动，收集到的雨水就是答案。一圈的柱子需要放在小根堆中。新增矩阵记录是否访问过。

时间复杂度：O(N*N*logN)。

空间复杂度：约O(N*N)。

代码用golang编写。代码如下：

package mainimport ( "fmt" "sort")func main() { heightMap := [][]int{ {1, 4, 3, 1, 3, 2}, {3, 2, 1, 3, 2, 4}, {2, 3, 3, 2, 3, 1}, } ret := trapRainWater(heightMap) fmt.Println(ret)}func trapRainWater(heightMap [][]int) int { if len(heightMap) == 0 || len(heightMap[0]) == 0 { return 0 } N := len(heightMap) M := len(heightMap[0]) isEnter := make([][]bool, N) for i := 0; i < N; i { isEnter[i] = make([]bool, M) } heap := make([]*Node, 0) for col := 0; col < M-1; col { isEnter[0][col] = true Push(&heap, NewNode(heightMap[0][col], 0, col)) } for row := 0; row < N-1; row { isEnter[row][M-1] = true Push(&heap, NewNode(heightMap[row][M-1], row, M-1)) } for col := M - 1; col > 0; col-- { isEnter[N-1][col] = true Push(&heap, NewNode(heightMap[N-1][col], N-1, col)) } for row := N - 1; row > 0; row-- { isEnter[row][0] = true Push(&heap, NewNode(heightMap[row][0], row, 0)) } water := 0 max := 0 for Len(&heap) > 0 { cur := Pop(&heap) max = getMax(max, cur.Val) r := cur.Row c := cur.Col if r > 0 && !isEnter[r-1][c] { water = getMax(0, max-heightMap[r-1][c]) isEnter[r-1][c] = true Push(&heap, NewNode(heightMap[r-1][c], r-1, c)) } if r < N-1 && !isEnter[r 1][c] { water = getMax(0, max-heightMap[r 1][c]) isEnter[r 1][c] = true Push(&heap, NewNode(heightMap[r 1][c], r 1, c)) } if c > 0 && !isEnter[r][c-1] { water = getMax(0, max-heightMap[r][c-1]) isEnter[r][c-1] = true Push(&heap, NewNode(heightMap[r][c-1], r, c-1)) } if c < M-1 && !isEnter[r][c 1] { water = getMax(0, max-heightMap[r][c 1]) isEnter[r][c 1] = true Push(&heap, NewNode(heightMap[r][c 1], r, c 1)) } } return water}type Node struct { Val int Row int Col int}func NewNode(v int, r int, c int) *Node { ret := &Node{} ret.Val = v ret.Row = r ret.Col = c return ret}func Push(heap *[]*Node, node *Node) { *heap = append(*heap, node)}func Pop(heap *[]*Node) *Node { sort.Slice(*heap, func(i, j int) bool { return (*heap)[i].Val < (*heap)[j].Val }) ans := (*heap)[0] *heap = (*heap)[1:] return ans}func Len(heap *[]*Node) int { return len(*heap)}func getMax(a int, b int) int { if a > b { return a } else { return b }}

执行结果如下：