题目描述
思路解析动画文字版
记住这套打法:所有水域格一起入队当第 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题