LeetCode 827困难图/并查集
最大人工岛 图解题解
这道题到底在问什么
给定 n×n 的 0/1 方阵 grid。最多把一个 0 改成 1,返回此时可能得到的最大岛屿(四连通的 1)面积。若全是 1,直接返回 n×n。
- 输入
- grid=[[1,1,0],[1,0,1],[0,1,1]]
- 输出
- 7(填中心 (1,1) 把左上、右下两座岛连起来)
先想最直接的笨办法
记住「先编号记面积 → 再枚举 0、四邻去重合并 +1」,下面逐帧套它。去重是关键:四条边可能都贴着同一座岛。（动画第 3 步）
最优解：一步一步想明白
- 3记住「先编号记面积 → 再枚举 0、四邻去重合并 +1」,下面逐帧套它。去重是关键:四条边可能都贴着同一座岛。
- 4第一阶段:给每座岛一个身份证。我们从左上到右下扫,碰到一个还是 1 的格子,就从它出发把整座岛染成同一个编号 id,顺手数出这座岛有几格。
- 5发现一座新岛,给它编号 id=2(就叫岛 A)。从 (0, 0) 起把它染成 2(绿色),开始一格一格往外扩。
- 6把同岛的 (0, 1) 也染成 2,面积累加到 2。
- 7把同岛的 (1, 0) 也染成 2,面积累加到 3。
- 8发现一座新岛,给它编号 id=3(就叫岛 B)。从 (1, 2) 起把它染成 3(绿色),开始一格一格往外扩。
- 9把同岛的 (2, 2) 也染成 3,面积累加到 2。
- 10把同岛的 (2, 1) 也染成 3,面积累加到 3。
- 11两座岛都编号好了:岛 A(id 2)有 3 格、岛 B(id 3)有 3 格。先记下:不填任何 0 时,最大的整岛是 3 格。接下来看填哪个 0 最划算。
- 12第二阶段:枚举每个海格 0。对一个 0,看它上下左右贴着哪些岛,用集合去重后把面积加起来、再加它自己这一格,拿去刷新答案。
- 13轮到海格 (0, 2)(紫色)。假设把它填成 1,看看它能把四周哪些岛连到一起。
- 14往下是 (1, 2),属于岛 B、面积 3,第一次遇到,计进集合,当前合并面积累计到 4(含填的这格)。
- 15往左是 (0, 1),属于岛 A、面积 3,第一次遇到,计进集合,当前合并面积累计到 7(含填的这格)。
- 16填 (0, 2) 能连出 7 格,比之前的 3 更大,刷新最大值为 7。
- 17轮到海格 (1, 1)(紫色)。假设把它填成 1,看看它能把四周哪些岛连到一起。
- 18往上是 (0, 1),属于岛 A、面积 3,第一次遇到,计进集合,当前合并面积累计到 4(含填的这格)。
- 19往下是 (2, 1),属于岛 B、面积 3,第一次遇到,计进集合,当前合并面积累计到 7(含填的这格)。
- 20往左是 (1, 0),它属于岛 A——这座岛刚才已经从另一条边数过了,集合里已有它,去重,不再重复加面积。
- 21往右是 (1, 2),它属于岛 B——这座岛刚才已经从另一条边数过了,集合里已有它,去重,不再重复加面积。
- 22填 (1, 1) 只能连出 7 格,没超过当前最大 7,保持不变。
- 23轮到海格 (2, 0)(紫色)。假设把它填成 1,看看它能把四周哪些岛连到一起。
- 24往上是 (1, 0),属于岛 A、面积 3,第一次遇到,计进集合,当前合并面积累计到 4(含填的这格)。
- 25往右是 (2, 1),属于岛 B、面积 3,第一次遇到,计进集合,当前合并面积累计到 7(含填的这格)。
- 26填 (2, 0) 只能连出 7 格,没超过当前最大 7,保持不变。
- 27所有海格都试过了。能把岛 A、岛 B 同时连上的填法都得到最大面积 7 格(本例填中心、填 (0,2)、填 (2,0) 都行);其中填中心那个 0 最典型,它四条边去重后正好接上 A、B,3 + 3 + 1 = 7 格。回头看:先给岛编号记面积、再枚举 0 去重合并,两遍扫网格就是 O(n²)。
⚠️ 容易写错的地方
✗ 错：四邻同属一座岛被重复加
✓ 对：用集合按 id 去重再求和
一个 0 的多条边可能都贴着同一座岛,不去重会把这座岛的面积加好几遍、答案虚高
✗ 错：id 从 0 或 1 开始
✓ 对：id 从 2 起
0 是海、1 是没标号的陆地,id 必须避开这两个值,否则没法区分「海/未标/某座岛」
✗ 错：忘了全是 1 的特判
✓ 对：先用已编号岛的最大面积初始化 ans,或没有 0 时直接返回 n×n
全 1 时枚举 0 的循环一次都不进;若只在那个循环里更新 ans、又没先用岛面积初始化,就会漏掉「本来就是整张岛」的答案
完整代码（Python / C++ / Java）
Python
from typing import List
class 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 ansC++
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size(), id = 2;
vector<int> area(2, 0);
function<int(int,int,int)> dfs = [&](int r, int c, int idx) {
if (r < 0 || r >= n || c < 0 || c >= n || 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);
};
for (int r = 0; r < n; ++r) for (int c = 0; c < n; ++c) if (grid[r][c] == 1) area.push_back(dfs(r, c, id++));
int ans = 0;
for (int x : area) ans = max(ans, x);
int dirs[5] = {1,0,-1,0,1};
for (int r = 0; r < n; ++r) for (int c = 0; c < n; ++c) if (grid[r][c] == 0) {
unordered_set<int> seen;
int cur = 1;
for (int d = 0; d < 4; ++d) {
int nr = r + dirs[d], nc = c + dirs[d+1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && seen.insert(grid[nr][nc]).second) cur += area[grid[nr][nc]];
}
ans = max(ans, cur);
}
return ans;
}
};Java
import java.util.*;
class Solution {
int[][] grid;
int n;
public int largestIsland(int[][] grid) {
this.grid = grid; n = grid.length;
List<Integer> area = new ArrayList<>();
area.add(0); area.add(0);
int id = 2;
for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) if (grid[r][c] == 1) area.add(dfs(r, c, id++));
int ans = 0;
for (int x : area) ans = Math.max(ans, x);
int[] dirs = {1,0,-1,0,1};
for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) if (grid[r][c] == 0) {
Set<Integer> seen = new HashSet<>();
int cur = 1;
for (int d = 0; d < 4; d++) {
int nr = r + dirs[d], nc = c + dirs[d + 1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && seen.add(grid[nr][nc])) cur += area.get(grid[nr][nc]);
}
ans = Math.max(ans, cur);
}
return ans;
}
private int dfs(int r, int c, int id) {
if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) return 0;
grid[r][c] = id;
return 1 + dfs(r+1,c,id) + dfs(r-1,c,id) + dfs(r,c+1,id) + dfs(r,c-1,id);
}
}复杂度
时间
O(n²)
第一遍 DFS 每个格子访问一次,第二遍枚举每个 0、各看常数个邻居;n×n 个格子合计 O(n²)
空间
O(n²)
area 表与 DFS 递归栈(或显式栈)最坏到 O(n²);id 直接写在 grid 上,省掉单独的 visited
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大人工岛 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么把 id 直接写回 grid,而不另开一个标记数组?+
因为染 id 这一步本身就兼做了「访问标记」:一个格子被改成某个 id 后就不再是 1,第一遍 DFS 不会再从它出发,等于省掉了单独的 visited 数组。同时这个 id 在第二遍还要被复用——枚举 0 时正是靠读邻居格里的 id 去查它属于哪座岛、面积多大。一份数据两用,空间更省。
能不能用并查集做?+
能。把每个 1 和它四连通的邻居 union 到一起,每个根记录所在集合的面积;枚举 0 时对四个邻居各 find 出根、用集合去重后把面积相加 +1。本质和 DFS 标号一样,只是「同一座岛」用并查集的根来表示、面积挂在根上,复杂度同为近似 O(n²)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大人工岛 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。