LC 1765. 地图中的最高点

题目描述

这是 LeetCode 上的 1765. 地图中的最高点 ，难度为 中等。

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由 陆地 和 水域 单元格组成的地图。

• 如果 isWater[i][j] == 0 ，格子 (i, j) 是一个 陆地 格子。
• 如果 isWater[i][j] == 1 ，格子 (i, j) 是一个 水域 格子。

你需要按照如下规则给每个单元格安排高度：

• 每个格子的高度都必须是非负的。
• 如果一个格子是是 水域 ，那么它的高度必须为 $0$ 。
• 任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）

找到一种安排高度的方案，使得矩阵中的最高高度值 最大 。

请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个 。

示例 1：

输入：isWater = [[0,1],[0,0]]

输出：[[1,0],[2,1]]

解释：上图展示了给各个格子安排的高度。
蓝色格子是水域格，绿色格子是陆地格。

示例 2：

输入：isWater = [[0,0,1],[1,0,0],[0,0,0]]

输出：[[1,1,0],[0,1,1],[1,2,2]]

解释：所有安排方案中，最高可行高度为 2 。
任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案。

提示：

• $m == isWater.length$
• $n == isWater[i].length$
• $1 <= m, n <= 1000$
• isWater[i][j] 要么是 $0$ ，要么是 $1$ 。
• 至少有 $1$ 个水域格子。

---

多源 BFS

这是一道「多源 BFS」板子题，对「多源 BFS」不熟悉的同学，可以看看前置 🧀：多源 BFS 入门。

里面详解了「多源 BFS」与「单源 BFS」板子上的区别，强调了可以通过建立「虚拟源点」的方式，将「多源 BFS」转换回「单源 BFS」问题。

回到本题，题目规定了水域区域的高度为 $0$，然后相邻格子之间的高度差至多为 $1$，

我们可以将所有水域（高度为 $0$）区域进行入队，然后跑一遍 BFS 即可。

将所有水域（高度为 $0$）区域进行入队的操作可看作是将与「虚拟源点」链接的节点进行入队（也等价于起始只将虚拟源点入队）：

容易证明这样做法的正确性：对于一个「陆地」区域（高度可变）而言，其所能填入的高度，取决于其距离其他「水域」区域的距离，而我们最终要让整个答案矩阵合法，因此每个「陆地」区域应该取其所能填入的高度的「下界」，即只由「距离它最近的水域」区域所更新，这符合 BFS 的性质。

代码（感谢 @Benhao 和 @5cm/s 🌸 同学提供的其他语言版本）：

class Solution {
    public int[][] highestPeak(int[][] g) {
        int m = g.length, n = g[0].length;
        int[][] ans = new int[m][n];
        Deque<int[]> d = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) d.addLast(new int[]{i, j});
                ans[i][j] = g[i][j] == 1 ? 0 : -1;
            }
        }
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        while (!d.isEmpty()) {
            int[] info = d.pollFirst();
            int x = info[0], y = info[1];
            for (int[] di : dirs) {
                int nx = x + di[0], ny = y + di[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (ans[nx][ny] != -1) continue;
                ans[nx][ny] = ans[x][y] + 1;
                d.addLast(new int[]{nx, ny});
            }
        }
        return ans;
    }
}

-

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m, n = len(isWater), len(isWater[0])
        ans = [[0] * n for _ in range(m)]
        d = deque()
        for i in range(m):
            for j in range(n):
                if isWater[i][j]:
                    d.append((i, j))
                ans[i][j] = 0 if isWater[i][j] else -1

        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        h = 1
        while d:
            size = len(d)
            for _ in range(size):
                x, y = d.popleft()
                for di in dirs:
                    nx, ny = x + di[0], y + di[1]
                    if 0 <= nx < m and 0 <= ny < n and ans[nx][ny] == -1:
                        ans[nx][ny] = h
                        d.append((nx, ny))
            h += 1
        return ans

-

func highestPeak(isWater [][]int) [][]int {
    m, n := len(isWater), len(isWater[0])
    ans, d := make([][]int, m), [][]int{}
    for i := 0; i < m; i++ {
        ans[i] = make([]int, n)
        for j := 0; j < n; j++ {
            if isWater[i][j] == 1 {
                d = append(d, []int{i, j})
                ans[i][j] = 0
            } else {
                ans[i][j] = -1
            }
        }
    }
    dirs := [][]int{{1,0}, {-1,0}, {0,1}, {0,-1}}
    for h := 1; len(d) > 0; h++ {
        for size := len(d); size > 0; size--{
            info := d[0]
            d = d[1:]
            x, y := info[0], info[1]
            for _, di := range dirs {
                nx, ny := x + di[0], y + di[1]
                if nx >= 0 && nx < m && ny >= 0 && ny < n && ans[nx][ny] == -1 {
                    ans[nx][ny] = h
                    d = append(d, []int{nx, ny})
                }
            }
        }
    }
    return ans
}

-

const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> ans(n, vector<int>(m, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (g[i][j] == 1) {
                    q.emplace(i, j);
                } else {
                    ans[i][j] = -1;
                }
            }
        }
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int a = x + dx[i], b = y + dy[i];
                if (a < 0 || a == n || b < 0 || b == m) continue;
                if (ans[a][b] >= 0) continue;
                ans[a][b] = ans[x][y] + 1;
                q.emplace(a, b);
            }
        }
        return ans;
    }
};

• 时间复杂度：$O(m * n)$
• 空间复杂度：$O(m * n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1765 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。