题目描述
思路解析
一句话答案：LeetCode 1765 地图里的最高点：水域高度定为 0，把所有水域格当第 0 层一起入队做多源广搜，逐层往外每步高度加 1，每格填上离最近水域的距离就是最高，时间 O(m·n)。
每格填个非负高度，让全图最高点尽量顶高
给一张 m 行 n 列的地图，isWater 里 1 是水域格、0 是陆地格。要给每格填一个非负高度：水域格必须是 0，任意相邻两格的高度差至多为 1。目标是让全图最高的那格尽量高，返回任意一种合法的高度矩阵。题面例子 isWater=[[0,1],[0,0]]，一种答案是 [[1,0],[2,1]]，最高点是 2。
逐格去量它离最近水域多远，慢在哪
相邻差至多为 1，意味着从任一水域格走一步、高度最多涨 1，走 k 步最多到 k。所以一个陆地格能填的最大高度，卡在它离最近水域的步数上。直接的办法是逐格去量：对每个陆地格各跑一趟广搜，一圈圈往外扩找最近水域。可 m·n 个格子、每趟扫大半张图，整体奔着 O((m·n)²) 去，图一大就吃不消。
为什么每格的高度，就是它离最近水域的步数
这些距离不必一格一格分开算。把所有水域格看成一条起跑线——它们高度都是 0，同时向四周扩散，谁的波前先碰到某个陆地格，那格就归谁、距离就此定下。这就是多源广搜：多个起点一起入队、按层齐头并进，某格第一次被触达在第几层，它离最近水域的距离就是几，填的高度就是几。一趟走完，最高点自然顶满。相邻只差 1 也成立：相邻两层距离本就差 1。
所有水域一起入队，波前怎么一层层往外填
落到代码上，先开一个和地图同样大的高度矩阵、全填 -1 表示还没定。扫一遍 isWater，把每个水域格的高度改成 0、坐标放进队列，这就是第 0 层。然后反复从队头取格子：看它上下左右四个邻居，只要某个邻居在界内、且高度还是 -1，就填成当前格高度加 1，再接到队尾。已经填过的邻居不再碰：第一次触达就是最短距离。队列空了，全图就填完了。
n=3 的小图，高度怎么一层层长出来
这张 3×3 小图 isWater=[[0,0,1],[1,0,0],[0,0,0]]，水域格就是 (0,2) 和 (1,0)，都填 0 入队当第 0 层。往外推：(0,2) 还没定的邻居是 (0,1)、(1,2)，(1,0) 的是 (0,0)、(1,1)、(2,0)，这五个都填 1，凑成第 1 层。再从这层往外：全图只剩 (2,1)、(2,2) 还是 -1，它们被第 1 层的格子触达，填 2，成第 2 层。此时再没有 -1。最终高度矩阵是 [[1,1,0],[0,1,1],[1,2,2]]，最高点是 2，正好落在离两个水源最远的右下角。
高度算错，多半是只认一个水源或填了又填
每个格子入队、出队各一次，出队只看四邻，总操作与格子数成正比，时间 O(m·n)；队列峰值最坏装下接近全图，空间 O(m·n)。容易写岔的是起跑那步：只从一个水域格出发、漏掉其余水源，离别处水源更近的格子会被算出更大距离、高度跟着错，所有水源必须一起入队当第 0 层。若不看邻居是否已定就赋值，同一格会被更长路径重复写、反复入队空转，只有它仍是 -1 时才填才拦得住。深搜随手填再回头修相邻差也白费：不按距离一层层展开，高度保不住处处只差 1。两种极端顺带想清：全是水时整张图都是 0；只有一个水源时退化成单源，每格高度就是到那水域的步数。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套打法:所有水域格一起入队当第 0 层,广搜按层往外推,某个陆地格第一次被触达在第几层,它的高度就是几。下面就一帧帧演这个波前扩散的过程。
认识地图 · 水域高度 0,陆地待定：这就是 4 行 4 列的地图。蓝色的两个角 (0,0) 和 (3,3) 是水域格,高度钉死为 0。其余灰色带问号的都是陆地格,高度还没定。咱们的任务就是把这些问号一个个填成尽量大的高度。
多源起点 · 所有水域格进队列当第 0 层：多源广搜的关键一步:把所有水域格一次性放进队列,当作第 0 层的波前。这里两个水源 (0,0) 和 (3,3) 一起入队。它们会同时向四周扩散,谁先碰到某个陆地格,那个格子就归谁管,算出来的自然是到最近水域的距离。
从水源 (0,0) · 高度 0：从队头取出水源格 (0,0),它的高度是 0。看它上下左右,四个邻居里还是问号的有 (0,1)、(1,0)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (0,0),所以它们的高度就是 0 加 1,也就是 1。
填高度 1 · (0,1) (1,0)：把 (0,1)、(1,0) 都填上高度 1,并接到队列末尾,让波前继续往外推。(0,0) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 4 个,还剩 12 个问号。
从水源 (3,3) · 高度 0：从队头取出水源格 (3,3),它的高度是 0。看它上下左右,四个邻居里还是问号的有 (2,3)、(3,2)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (3,3),所以它们的高度就是 0 加 1,也就是 1。
填高度 1 · (2,3) (3,2)：把 (2,3)、(3,2) 都填上高度 1,并接到队列末尾,让波前继续往外推。(3,3) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 6 个,还剩 10 个问号。
扩展 (0,1) · 高度 1：从队头取出格子 (0,1),它的高度是 1。看它上下左右,四个邻居里还是问号的有 (0,2)、(1,1)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (0,1),所以它们的高度就是 1 加 1,也就是 2。
填高度 2 · (0,2) (1,1)：把 (0,2)、(1,1) 都填上高度 2,并接到队列末尾,让波前继续往外推。(0,1) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 8 个,还剩 8 个问号。
扩展 (1,0) · 高度 1：从队头取出格子 (1,0),它的高度是 1。看它上下左右,四个邻居里还是问号的有 (2,0)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (1,0),所以它们的高度就是 1 加 1,也就是 2。
填高度 2 · (2,0)：把 (2,0) 都填上高度 2,并接到队列末尾,让波前继续往外推。(1,0) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 9 个,还剩 7 个问号。
扩展 (2,3) · 高度 1：从队头取出格子 (2,3),它的高度是 1。看它上下左右,四个邻居里还是问号的有 (1,3)、(2,2)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (2,3),所以它们的高度就是 1 加 1,也就是 2。
填高度 2 · (1,3) (2,2)：把 (1,3)、(2,2) 都填上高度 2,并接到队列末尾,让波前继续往外推。(2,3) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 11 个,还剩 5 个问号。
扩展 (3,2) · 高度 1：从队头取出格子 (3,2),它的高度是 1。看它上下左右,四个邻居里还是问号的有 (3,1)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (3,2),所以它们的高度就是 1 加 1,也就是 2。
填高度 2 · (3,1)：把 (3,1) 都填上高度 2,并接到队列末尾,让波前继续往外推。(3,2) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 12 个,还剩 4 个问号。
扩展 (0,2) · 高度 2：从队头取出格子 (0,2),它的高度是 2。看它上下左右,四个邻居里还是问号的有 (0,3)、(1,2)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (0,2),所以它们的高度就是 2 加 1,也就是 3。
填高度 3 · (0,3) (1,2)：把 (0,3)、(1,2) 都填上高度 3,并接到队列末尾,让波前继续往外推。(0,2) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 14 个,还剩 2 个问号。
扩展 (1,1) · 高度 2：从队头取出格子 (1,1),它的高度是 2。看它上下左右,四个邻居里还是问号的有 (2,1)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (1,1),所以它们的高度就是 2 加 1,也就是 3。
填高度 3 · (2,1)：把 (2,1) 都填上高度 3,并接到队列末尾,让波前继续往外推。(1,1) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 15 个,还剩 1 个问号。
扩展 (2,0) · 高度 2：从队头取出格子 (2,0),它的高度是 2。看它上下左右,四个邻居里还是问号的有 (3,0)。这些格子这是第一次被波前碰到,通往它们的最近路径正好经过 (2,0),所以它们的高度就是 2 加 1,也就是 3。
填高度 3 · (3,0)：把 (3,0) 都填上高度 3,并接到队列末尾,让波前继续往外推。(2,0) 的四邻处理完了,标成已扩展。现在已经定好高度的格子有 16 个,还剩 0 个问号。
波前收束 · 剩余格子四邻已定：到这里所有格子都已经填好了高度。刚弹出的 (1,3) 高度是 2,看它四周,邻居全都有高度了,没有新的问号可以填,这次弹出等于空转。队列里剩下的 6 个格子也是同样情况,一个个弹出去都不会再改动任何格子,波前到此为止。
答案 · 最高点 = 3：波前扩散完,整张高度图就出来了。两个角上的水域是 0,越往中间的对角线走高度越大。离两个水源都最远的几个格子取到了最高高度 3,橙色高亮的就是它们。这就是这张地图能安排出的最高点,答案矩阵每一格都满足相邻差至多为 1。
边界想清:一个水源时高度就是到它的步数、离水源最远处是最高点、全水域时整张图都是 0。
面试重点:广搜按层保证第一次写入即最短、本题与 542 零一矩阵是同一道、也可用两遍扫描的动态规划等价求解。
参考代码
from __future__ import annotationsfrom 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 = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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 ans复杂度
- 时间：O(m·n)，m 是行数,n 是列数。每个格子最多入队一次、出队一次,出队时看它的四个邻居,常数次操作。总共 m 乘 n 个格子,所以是 O(m·n)
- 空间：O(m·n)，队列最坏会同时装下接近全部格子(如果水域格很多,甚至几乎整张图都是水,初始化时会一次性把这些水域格都入队,队列瞬时就接近全部格子),按峰值是 O(m·n)。答案矩阵是题目要求返回的输出,通常不额外计入辅助空间
易错点
面试追问把动画讲成自己的话
追问为什么广搜第一次写入某个格子的高度,就一定是它的最短距离,不会被后面覆盖?
追问这道题和 542 题零一矩阵是什么关系?
追问除了广搜,还有别的解法吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
移动所有球到每个盒子所需的最小操作数
LeetCode 1769 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题