岛屿最大面积:淹岛时把格子数带回来
数的不是岛屿座数,是最大那座有几格。扫到 1 就 DFS 淹没,返回 1+四邻面积,全程只留一个 best。
越界或水返回 0。走进陆地立刻置 0,面积 = 1 + 上下左右 DFS 之和。外层每发现一个还是 1 的格子就开一次淹没,用返回值更新 best。每格只进一次。时间 O(m·n),空间 O(m·n)。
这是 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 只出现一次,连通块大小才准。
Go:淹没返回面积
func maxAreaOfIsland(grid [][]int) int {m, n := len(grid), len(grid[0])var dfs func(int, int) intdfs = func(i, j int) int {if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 { return 0 }grid[i][j] = 0return 1 + dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1)}best := 0for 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。