题目描述
思路解析动画文字版
记住「先编号记面积 → 再枚举 0、四邻去重合并 +1」,下面逐帧套它。去重是关键:四条边可能都贴着同一座岛。
第一阶段:给每座岛一个身份证。我们从左上到右下扫,碰到一个还是 1 的格子,就从它出发把整座岛染成同一个编号 id,顺手数出这座岛有几格。
发现一座新岛,给它编号 id=2(就叫岛 A)。从 (0, 0) 起把它染成 2(绿色),开始一格一格往外扩。
把同岛的 (0, 1) 也染成 2,面积累加到 2。
把同岛的 (1, 0) 也染成 2,面积累加到 3。
发现一座新岛,给它编号 id=3(就叫岛 B)。从 (1, 2) 起把它染成 3(绿色),开始一格一格往外扩。
把同岛的 (2, 2) 也染成 3,面积累加到 2。
把同岛的 (2, 1) 也染成 3,面积累加到 3。
两座岛都编号好了:岛 A(id 2)有 3 格、岛 B(id 3)有 3 格。先记下:不填任何 0 时,最大的整岛是 3 格。接下来看填哪个 0 最划算。
第二阶段:枚举每个海格 0。对一个 0,看它上下左右贴着哪些岛,用集合去重后把面积加起来、再加它自己这一格,拿去刷新答案。
轮到海格 (0, 2)(紫色)。假设把它填成 1,看看它能把四周哪些岛连到一起。
往下是 (1, 2),属于岛 B、面积 3,第一次遇到,计进集合,当前合并面积累计到 4(含填的这格)。
往左是 (0, 1),属于岛 A、面积 3,第一次遇到,计进集合,当前合并面积累计到 7(含填的这格)。
填 (0, 2) 能连出 7 格,比之前的 3 更大,刷新最大值为 7。
轮到海格 (1, 1)(紫色)。假设把它填成 1,看看它能把四周哪些岛连到一起。
往上是 (0, 1),属于岛 A、面积 3,第一次遇到,计进集合,当前合并面积累计到 4(含填的这格)。
往下是 (2, 1),属于岛 B、面积 3,第一次遇到,计进集合,当前合并面积累计到 7(含填的这格)。
往左是 (1, 0),它属于岛 A——这座岛刚才已经从另一条边数过了,集合里已有它,去重,不再重复加面积。
往右是 (1, 2),它属于岛 B——这座岛刚才已经从另一条边数过了,集合里已有它,去重,不再重复加面积。
填 (1, 1) 只能连出 7 格,没超过当前最大 7,保持不变。
轮到海格 (2, 0)(紫色)。假设把它填成 1,看看它能把四周哪些岛连到一起。
往上是 (1, 0),属于岛 A、面积 3,第一次遇到,计进集合,当前合并面积累计到 4(含填的这格)。
往右是 (2, 1),属于岛 B、面积 3,第一次遇到,计进集合,当前合并面积累计到 7(含填的这格)。
填 (2, 0) 只能连出 7 格,没超过当前最大 7,保持不变。
所有海格都试过了。能把岛 A、岛 B 同时连上的填法都得到最大面积 7 格(本例填中心、填 (0,2)、填 (2,0) 都行);其中填中心那个 0 最典型,它四条边去重后正好接上 A、B,3 + 3 + 1 = 7 格。回头看:先给岛编号记面积、再枚举 0 去重合并,两遍扫网格就是 O(n²)。
边界:全 1 是 n²、全 0 是 1、孤立 0 只得 1。
两个高频追问:id 写回 grid 兼当标记;也可用并查集等价实现。
参考代码
from typing import Listclass Solution: def largestIsland(self, grid: List[List[int]]) -> int: n = len(grid) area = {0: 0} def dfs(r, c, idx): if r < 0 or r >= n or c < 0 or c >= n or grid[r][c] != 1: return 0 grid[r][c] = idx return 1 + dfs(r+1,c,idx) + dfs(r-1,c,idx) + dfs(r,c+1,idx) + dfs(r,c-1,idx) idx = 2 for r in range(n): for c in range(n): if grid[r][c] == 1: area[idx] = dfs(r, c, idx) idx += 1 ans = max(area.values()) for r in range(n): for c in range(n): if grid[r][c] == 0: seen = {grid[nr][nc] for nr, nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)) if 0 <= nr < n and 0 <= nc < n} ans = max(ans, 1 + sum(area[x] for x in seen)) return ans复杂度
- 时间：O(n²)，第一遍 DFS 每个格子访问一次,第二遍枚举每个 0、各看常数个邻居;n×n 个格子合计 O(n²)
- 空间：O(n²)，area 表与 DFS 递归栈(或显式栈)最坏到 O(n²);id 直接写在 grid 上,省掉单独的 visited
易错点
面试追问把动画讲成自己的话
追问为什么把 id 直接写回 grid,而不另开一个标记数组?
追问能不能用并查集做?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
网格中的最短路径(可消除障碍)
LeetCode 1293 · 困难 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题