LeetCode 407. 接雨水 II

Categories:

题目描述
思路分析
1. 解法一：最小堆 + BFS（推荐）
相似题目

题目描述

✅ 407. 接雨水 II

思路分析

解法一：最小堆 + BFS（推荐）

核心思路：

从边界开始作为初始“围墙”，使用最小堆维护当前最低的围墙高度。

每次弹出最低围墙，向四周扩展，若邻居高度更低则可蓄水。

将邻居加入堆时高度取 max(当前围墙高度, 邻居高度)。

复杂度分析：

时间复杂度：O(mn log mn)，其中 m、n 为网格行列数。

空间复杂度：O(mn)。

{% raw %}

// 最小堆 + BFS 计算接雨水
class Solution {
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length;
        int n = heightMap[0].length;
        if (m <= 2 || n <= 2) {
            return 0;
        }

        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);

        for (int i = 0; i < m; i++) {
            pq.offer(new int[]{i, 0, heightMap[i][0]});
            pq.offer(new int[]{i, n - 1, heightMap[i][n - 1]});
            visited[i][0] = true;
            visited[i][n - 1] = true;
        }
        for (int j = 1; j < n - 1; j++) {
            pq.offer(new int[]{0, j, heightMap[0][j]});
            pq.offer(new int[]{m - 1, j, heightMap[m - 1][j]});
            visited[0][j] = true;
            visited[m - 1][j] = true;
        }

        int res = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            for (int[] d : dirs) {
                int x = cur[0] + d[0];
                int y = cur[1] + d[1];
                if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) {
                    continue;
                }
                visited[x][y] = true;
                int h = heightMap[x][y];
                if (h < cur[2]) {
                    res += cur[2] - h;
                }
                pq.offer(new int[]{x, y, Math.max(h, cur[2])});
            }
        }

        return res;
    }
}

{% endraw %}

{% raw %}

// 最小堆 + BFS 计算接雨水
func trapRainWater(heightMap [][]int) int {
	m := len(heightMap)
	n := len(heightMap[0])
	if m <= 2 || n <= 2 {
		return 0
	}

	visited := make([][]bool, m)
	for i := range visited {
		visited[i] = make([]bool, n)
	}

	pq := &MinHeap{}
	heap.Init(pq)

	for i := 0; i < m; i++ {
		heap.Push(pq, Cell{i, 0, heightMap[i][0]})
		heap.Push(pq, Cell{i, n - 1, heightMap[i][n-1]})
		visited[i][0] = true
		visited[i][n-1] = true
	}
	for j := 1; j < n-1; j++ {
		heap.Push(pq, Cell{0, j, heightMap[0][j]})
		heap.Push(pq, Cell{m - 1, j, heightMap[m-1][j]})
		visited[0][j] = true
		visited[m-1][j] = true
	}

	res := 0
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	for pq.Len() > 0 {
		cur := heap.Pop(pq).(Cell)
		for _, d := range dirs {
			x := cur.x + d[0]
			y := cur.y + d[1]
			if x < 0 || x >= m || y < 0 || y >= n || visited[x][y] {
				continue
			}
			visited[x][y] = true
			h := heightMap[x][y]
			if h < cur.h {
				res += cur.h - h
			}
			if h < cur.h {
				h = cur.h
			}
			heap.Push(pq, Cell{x, y, h})
		}
	}

	return res
}

type Cell struct {
	x, y int
	h    int
}

type MinHeap []Cell

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i].h < h[j].h }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Cell)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	v := old[n-1]
	*h = old[:n-1]
	return v
}

{% endraw %}

相似题目

题目	难度	考察点
42. 接雨水	困难	双指针/单调栈
407. 接雨水 II	困难	堆/BFS
778. 水位上升的泳池中游泳	困难	堆/BFS
1162. 地图分析	中等	BFS
1091. 二进制矩阵中的最短路径	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/34609866