当前:LC695 · 岛屿的最大面积 · 首次出现于 Day 29 · 路径:顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

LC695 · Max Area of Island · 网格 / DFS

岛屿最大面积:淹岛时把格子数带回来

数的不是岛屿座数,是最大那座有几格。扫到 1 就 DFS 淹没,返回 1+四邻面积,全程只留一个 best。

越界或水返回 0。走进陆地立刻置 0,面积 = 1 + 上下左右 DFS 之和。外层每发现一个还是 1 的格子就开一次淹没,用返回值更新 best。每格只进一次。时间 O(m·n),空间 O(m·n)。

时间 O(m·n)空间 O(m·n)结论先行 · 全文约 6 节
导读

这是 LeetCode 695. Max Area of Island。网格里 1 是陆地、0 是水,上下左右相连算同一座岛,对角线不相连。求最大一座岛的面积;全是水则 0。

主例 4×4:第一行 0 0 1 0,第二行 0 1 1 0,第三行 0 1 0 0,第四行 0 0 1 1。左上 (0,2)、(1,2)、(1,1)、(2,1) 连成 4 格;右下 (3,2)、(3,3) 是 2 格。答案 4。

第一直觉是看见 1 就 +1,那是在数陆地格子总数,主例会得到 6。LC200 的淹没只加座数,不记每座多大。缺的是「一次 DFS 返回连通块大小」。下面从这块缺口把计数接进淹没。

淹没的返回值就是这座岛的面积

网格仍是隐式图:陆地是点,四邻陆地是边。LC200 外层发现新岛就 +1,内层把连通块改成水。本题外层不再加座数,改为比较这座岛有多大。

缺的信息是「当前连通块包含几格」。若在外层另开一个计数器、每走进一格 +1,和 DFS 返回值是同一件事,但返回值把「这块有多大」变成函数契约:调用者拿到一个数,直接和 best 比。不标记就重复走进同一格,面积会爆;先标记再递归,每格只贡献 1。

从缺口写出 DFS。越界、已经是 0,返回 0。否则把当前格改成 0,返回 1 加上四个方向的返回值。外层双重循环扫到 1,才调用一次 DFS,用返回值更新 best。对角线不是邻居,写进去就改了题意。

用手走主例。扫到 (0,2) 是 1,开始淹,area 先记 1,best=1,演示第一帧停在这里。DFS 向四邻扩:下是 (1,2),左是没有陆地,右是水。从 (1,2) 再扩到 (1,1),从 (1,1) 再扩到 (2,1)。四格都置 0,返回 4,best=4。演示第二帧 cur 在 (2,1),标出这四格。继续扫,左上已是水。扫到 (3,2),新岛面积 2,best 仍是 4。演示第三帧在 (3,3)。全图扫完,答案 4。

best 必须在每次 DFS 返回之后更新,不能等全部格子走完再数 1——那些 1 已经被淹成 0。空图 best 保持 0。每个格子进出常数次,时间 O(m·n);递归深度最坏整张陆地,空间 O(m·n)。

先置 0 再递归走进格子立刻改成水,这格就不会被四个方向重复加进面积。返回值 1 只出现一次,连通块大小才准。
grid 4×4
0
0
1
0
0
1
1
0
0
1
0
0
0
0
1
1
当前岛 1/最大 1
(0,2) 发现岛,开始统计

Go:淹没返回面积

solution.goGo
func maxAreaOfIsland(grid [][]int) int {
m, n := len(grid), len(grid[0])
var dfs func(int, int) int
dfs = func(i, j int) int {
if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 { return 0 }
grid[i][j] = 0
return 1 + dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1)
}
best := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
if a := dfs(i, j); a > best { best = a }
}
}
}
return best
}

1越界或水返回 0,这是「没有这块面积」。守卫必须写在读邻居之前。

2grid[i][j]=0 立刻标记。主例 (0,2) 进过一次,四邻再指回来也是 0。

31 + 四向之和就是连通块大小。外层只在还是 1 的格子启动,并用返回值挑战 best。

4主例先返回 4,再返回 2,best 停在 4。

总结

发现陆地就淹,DFS 返回面积,best 取最大。主例 4 对 2,答案 4。

  • 数格子总数、数岛屿座数,都不是本题。要的是单座最大。
  • 先置 0 再递归,每格只给面积贡献 1。
  • best 在每次淹没返回后更新;格子已被改成 0,事后数 1 会得到 0。
同族题目
LC200岛屿数量LC1254统计封闭岛屿的数目LC827最大人工岛