LeetCode 1765中等数组 · 哈希
地图中的最高点 图解题解
这道题到底在问什么
给你一个 m 行 n 列的矩阵 isWater,值为 1 的是水域格,值为 0 的是陆地格。请给每个格子安排一个非负高度:水域格高度必须为 0,任意相邻两格高度差至多为 1。要让矩阵里的最高高度尽可能大,返回任意一种满足条件的高度矩阵。
- 输入
- isWater=[[0,1],[0,0]]
- 输出
- [[1,0],[2,1]]
- 输入
- isWater=[[0,0,1],[1,0,0],[0,0,0]]
- 输出
- [[1,1,0],[0,1,1],[1,2,2]]
最优解：一步一步想明白
- 3记住这套打法:所有水域格一起入队当第 0 层,广搜按层往外推,某个陆地格第一次被触达在第几层,它的高度就是几。下面就一帧帧演这个波前扩散的过程。
- 4蓝 = 水域(高度 0),灰问号 = 陆地(高度未定)这就是 4 行 4 列的地图。蓝色的两个角 (0,0) 和 (3,3) 是水域格,高度钉死为 0。其余灰色带问号的都是陆地格,高度还没定。咱们的任务就是把这些问号一个个填成尽量大的高度。
- 5两个水源同时入队,准备一起向外扩散多源广搜的关键一步:把所有水域格一次性放进队列,当作第 0 层的波前。这里两个水源 (0,0) 和 (3,3) 一起入队。它们会同时向四周扩散,谁先碰到某个陆地格,那个格子就归谁管,算出来的自然是到最近水域的距离。
- 6橙 = 正在扩展,浅橙 = 即将被触达的问号邻居从队头取出水源格 (0,0),它的高度是 0。看它上下左右,四个邻居里还是问号的有 (0,1)、(1,0)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (0,0),所以它们的高度就是 0 加 1,也就是 1。
- 7刚填好的格子高度 = 1,已入队等待继续扩散把 (0,1)、(1,0) 都填上高度 1,并接到队列末尾,让波前继续往外推。(0,0) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 4 个,还剩 12 个问号。
- 8橙 = 正在扩展,浅橙 = 即将被触达的问号邻居从队头取出水源格 (3,3),它的高度是 0。看它上下左右,四个邻居里还是问号的有 (2,3)、(3,2)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (3,3),所以它们的高度就是 0 加 1,也就是 1。
- 9刚填好的格子高度 = 1,已入队等待继续扩散把 (2,3)、(3,2) 都填上高度 1,并接到队列末尾,让波前继续往外推。(3,3) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 6 个,还剩 10 个问号。
- 10橙 = 正在扩展,浅橙 = 即将被触达的问号邻居从队头取出格子 (0,1),它的高度是 1。看它上下左右,四个邻居里还是问号的有 (0,2)、(1,1)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (0,1),所以它们的高度就是 1 加 1,也就是 2。
- 11刚填好的格子高度 = 2,已入队等待继续扩散把 (0,2)、(1,1) 都填上高度 2,并接到队列末尾,让波前继续往外推。(0,1) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 8 个,还剩 8 个问号。
- 12橙 = 正在扩展,浅橙 = 即将被触达的问号邻居从队头取出格子 (1,0),它的高度是 1。看它上下左右,四个邻居里还是问号的有 (2,0)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (1,0),所以它们的高度就是 1 加 1,也就是 2。
- 13刚填好的格子高度 = 2,已入队等待继续扩散把 (2,0) 都填上高度 2,并接到队列末尾,让波前继续往外推。(1,0) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 9 个,还剩 7 个问号。
- 14橙 = 正在扩展,浅橙 = 即将被触达的问号邻居从队头取出格子 (2,3),它的高度是 1。看它上下左右,四个邻居里还是问号的有 (1,3)、(2,2)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (2,3),所以它们的高度就是 1 加 1,也就是 2。
- 15刚填好的格子高度 = 2,已入队等待继续扩散把 (1,3)、(2,2) 都填上高度 2,并接到队列末尾,让波前继续往外推。(2,3) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 11 个,还剩 5 个问号。
- 16橙 = 正在扩展,浅橙 = 即将被触达的问号邻居从队头取出格子 (3,2),它的高度是 1。看它上下左右,四个邻居里还是问号的有 (3,1)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (3,2),所以它们的高度就是 1 加 1,也就是 2。
- 17刚填好的格子高度 = 2,已入队等待继续扩散把 (3,1) 都填上高度 2,并接到队列末尾,让波前继续往外推。(3,2) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 12 个,还剩 4 个问号。
- 18橙 = 正在扩展,浅橙 = 即将被触达的问号邻居从队头取出格子 (0,2),它的高度是 2。看它上下左右,四个邻居里还是问号的有 (0,3)、(1,2)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (0,2),所以它们的高度就是 2 加 1,也就是 3。
- 19刚填好的格子高度 = 3,已入队等待继续扩散把 (0,3)、(1,2) 都填上高度 3,并接到队列末尾,让波前继续往外推。(0,2) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 14 个,还剩 2 个问号。
- 20橙 = 正在扩展,浅橙 = 即将被触达的问号邻居从队头取出格子 (1,1),它的高度是 2。看它上下左右,四个邻居里还是问号的有 (2,1)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (1,1),所以它们的高度就是 2 加 1,也就是 3。
- 21刚填好的格子高度 = 3,已入队等待继续扩散把 (2,1) 都填上高度 3,并接到队列末尾,让波前继续往外推。(1,1) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 15 个,还剩 1 个问号。
- 22橙 = 正在扩展,浅橙 = 即将被触达的问号邻居从队头取出格子 (2,0),它的高度是 2。看它上下左右,四个邻居里还是问号的有 (3,0)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (2,0),所以它们的高度就是 2 加 1,也就是 3。
- 23刚填好的格子高度 = 3,已入队等待继续扩散把 (3,0) 都填上高度 3,并接到队列末尾,让波前继续往外推。(2,0) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 16 个,还剩 0 个问号。
- 24所有格子都已填好高度,队列里剩下的弹出也不再更新到这里所有格子都已经填好了高度。刚弹出的 (1,3) 高度是 2,看它四周,邻居全都有高度了,没有新的问号可以填,这次弹出等于空转。队列里剩下的 6 个格子也是同样情况,一个个弹出去都不会再改动任何格子,波前到此为止。
- 25橙 = 取到最高高度 3 的格子波前扩散完,整张高度图就出来了。两个角上的水域是 0,越往中间的对角线走高度越大。离两个水源都最远的几个格子取到了最高高度 3,橙色高亮的就是它们。这就是这张地图能安排出的最高点,答案矩阵每一格都满足相邻差至多为 1。
⚠️ 容易写错的地方
✗ 错：只从一个水域格开始 BFS,漏掉其它水域格
✓ 对：所有水域格必须一起入队,当第 0 层多源出发
有多个水源时,某个陆地格离哪个水源近就该归哪个;只从一个水源跑会把距离算大,高度就错了
✗ 错：不判邻居是否已定就赋值,导致一个格子被写多次
✓ 对：只在邻居高度还是 -1(未定)时才赋值并入队
广搜第一次触达就是最短距离,后面更长的路径若再覆盖,高度会被改大、还会重复入队死循环
✗ 错：想用深搜或随手填,再回头修相邻差
✓ 对：按层广搜天生保证相邻差至多为 1
深搜不按距离顺序展开,填出来的高度不是最短距离,很难保证处处相邻差至多为 1
✗ 错：忘了水域格高度固定为 0 或忘判越界
✓ 对：水域格初始就是 0 且作为起点,扩散时先判在界内
水域格是整个高度体系的锚点,值错了全盘皆错;越界不判会数组下标出错
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
m, n = len(isWater), len(isWater[0])
ans = [[-1] * n for _ in range(m)]
q = deque()
for i, row in enumerate(isWater):
for j, v in enumerate(row):
if v:
q.append((i, j))
ans[i][j] = 0
while q:
i, j = q.popleft()
for a, b in pairwise((-1, 0, 1, 0, -1)):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:
ans[x][y] = ans[i][j] + 1
q.append((x, y))
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
const int dirs[5] = {-1, 0, 1, 0, -1};
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int m = isWater.size(), n = isWater[0].size();
vector<vector<int>> ans(m, vector<int>(n));
queue<pair<int, int>> q;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans[i][j] = isWater[i][j] - 1;
if (ans[i][j] == 0) {
q.emplace(i, j);
}
}
}
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1) {
ans[x][y] = ans[i][j] + 1;
q.emplace(x, y);
}
}
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int[][] highestPeak(int[][] isWater) {
int m = isWater.length, n = isWater[0].length;
int[][] ans = new int[m][n];
Deque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans[i][j] = isWater[i][j] - 1;
if (ans[i][j] == 0) {
q.offer(new int[] {i, j});
}
}
}
int[] dirs = {-1, 0, 1, 0, -1};
while (!q.isEmpty()) {
int[] p = q.poll();
int i = p[0], j = p[1];
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1) {
ans[x][y] = ans[i][j] + 1;
q.offer(new int[] {x, y});
}
}
}
return ans;
}
}复杂度
时间
O(m·n)
m 是行数,n 是列数。每个格子最多入队一次、出队一次,出队时看它的四个邻居,常数次操作。总共 m 乘 n 个格子,所以是 O(m·n)
空间
O(m·n)
队列最坏会同时装下接近全部格子(如果水域格很多,甚至几乎整张图都是水,初始化时会一次性把这些水域格都入队,队列瞬时就接近全部格子),按峰值是 O(m·n)。答案矩阵是题目要求返回的输出,通常不额外计入辅助空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 地图中的最高点 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么广搜第一次写入某个格子的高度,就一定是它的最短距离,不会被后面覆盖?+
广搜是按层扩散的,队列里先进先出,保证了先处理离水源近的格子,再处理远的。所以任何一个格子第一次被某个邻居触达时,那个邻居一定属于更靠内的一层,得到的高度就是最短步数。后面即使还有别的路径能走到它,那条路径只会更长或相等,代码里用「高度还是 -1 才赋值」把它挡在门外,第一次写入的值就锁定了,不会被改大。
这道题和 542 题零一矩阵是什么关系?+
本质是同一道题。542 给你一个零一矩阵,让你求每个格子到最近的 0 的距离。把本题的水域格看成 0,陆地格看成 1,要求的高度就是每个陆地格到最近水域的距离,和 542 求到最近 0 的距离一模一样。所以两题都能用多源广搜:把所有 0,也就是水域,当第 0 层一起入队扩散。
除了广搜,还有别的解法吗?+
有。542 那道题的经典做法是动态规划两遍扫描:第一遍从左上往右下扫,每个格子的距离由上方和左方的邻居加 1 取最小;第二遍从右下往左上扫,再由下方和右方的邻居加 1 取最小,两遍合起来就得到到最近水域的距离。它和广搜结果相同、复杂度也都是 O(m 乘 n),只是广搜更直观,把波前扩散画出来更好理解,所以本节动画走的是广搜。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 地图中的最高点 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。