LeetCode LCR 105. 岛屿的最大面积

2026-03-28 HGNULB 约 10 分钟

文章信息 5 个分类 6 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 105. 岛屿的最大面积

题意分析

给一个由 0 和 1 组成的二维网格，1 表示陆地。相邻（只算上下左右四个方向）的陆地属于同一座岛，问最大的一座岛占多少个格子；没有陆地时返回 0。

「相邻的陆地属于同一座岛」本质上是在网格上定义了一张隐式的图：每个陆地格是一个点，上下左右相邻的两个陆地格之间有一条边。题目要的是最大连通块的大小。这是网格题里最典型的建模，值得在面试里第一句就说出来。

约束里 m, n ≤ 50，总格子数不超过 2500，规模极小，说明只要做到每个格子被访问常数次就足够，不需要任何优化技巧；重点考的是遍历的写法是否干净、边界是否处理正确。

「四个方向」这个限定要特别留意：如果误按八方向搜索，对角相连的两块陆地会被并成一座岛，面积直接算大。题面里这类方向约定是必须逐字核对的信息。

还有一条隐含要求：每个陆地格只能被计入一座岛、且只能被计一次。也就是说遍历过程中必须有一种「已访问」的标记机制，否则同一块陆地会沿着不同路径被反复累加，面积无限膨胀甚至递归不终止。

边界：网格全是 0 时答案为 0；整张网格全是 1 时答案是 m * n；单行、单列的网格必须能被同一套下标判断安全覆盖。

解法：并查集维护连通性

核心思路

最朴素的想法是：对每个陆地格出发做一次搜索，数出它所在连通块的大小，再取最大。问题在于同一座岛上有多少个格子，就会被完整搜索多少次，复杂度退化到 $O((mn)^2)$。

瓶颈显然是重复搜索同一个连通块。既然一座岛只需要被量一次，那么在搜索过程中就应该把走过的陆地「消掉」，让它不会再作为新的起点、也不会在同一次搜索里被二次计数。

于是得到这条不变量：任何时刻，grid 中值为 1 的格子都是「尚未被计入任何一座岛」的格子。搜索一进入某个陆地格就立刻把它置 0，这条不变量就在整个过程中始终成立。它同时承担了两件事——防止同一次深搜绕圈无限递归，以及保证外层双重循环不会从已数过的岛上重新起跳。

有了这条不变量，递归函数的语义就可以定得非常干净：dfs(i, j) 返回「从 (i, j) 出发、沿着尚未被消除的陆地能到达的格子总数」。它有两条分支——若 (i, j) 不是陆地（越界之外的情形已在调用前挡住），返回 0；否则先把自己置 0 并计 1，再把四个方向的返回值累加上来。

因为整张网格被这样「淹没」一遍，每个格子最多被置 0 一次、被访问常数次，总代价是线性的。外层双重循环对每个格子调用一次 dfs 并取最大值：落在已淹没区域的调用会立刻返回 0，不产生额外开销；落在新岛上的调用则一次性量出整座岛的面积。

这种「就地改写输入当访问标记」的写法省掉了 visited 数组，代价是破坏了入参。面试时应当主动说明这一点，并补一句「如果调用方不允许修改入参，就换成同规模的 visited 布尔数组，复杂度不变」。

解题步骤

记录 m、n 并把 grid 存起来供递归访问。为什么：递归函数每一层都要判越界和取值，把行列数与网格提到共享位置可以避免层层传参，也让递归签名保持成 (i, j) 这两个真正变化的量。

外层双重循环遍历每个格子，用 answer = max(answer, dfs(i, j)) 更新答案。为什么要对每个格子都调用而不是只对陆地调用：dfs 内部第一行就会判掉非陆地并返回 0，把判断收敛到一个地方，主循环更干净；也避免了「主循环判一次、递归里再判一次」的重复逻辑。

dfs 第一行判 grid[i][j] == 0 则返回 0。为什么是返回 0 而不是抛错：这一行同时覆盖了三种情况——本来就是海水、已经被淹没过、以及从邻居递归过来时撞上非陆地，统一用「贡献 0 个格子」表达，语义自洽。

确认是陆地后，先把 grid[i][j] = 0，再向四周递归。为什么顺序不能反：如果先递归再置 0，邻居会沿着 (i,j) 走回来，两个格子互相递归，直接栈溢出。置 0 必须发生在任何递归调用之前，这是本题的铁律。

用方向数组 {-1, 0, 1, 0, -1} 配合 dirs[k]、dirs[k+1] 取出四个偏移。为什么这么写：五个元素的滑动窗口恰好给出 (-1,0)、(0,1)、(1,0)、(0,-1) 四组偏移，比写四段重复的 if 短且不易漏；同时它天然只含四方向，不会误引入对角线。

递归前判 0 <= x < m && 0 <= y < n。为什么在调用点判而不是在函数入口判：入口判也可以，但放在调用点能让 dfs 的入参始终保证合法，函数体内不必再考虑越界，两处只需维护一处约定。

返回累加值 answer，初值为 1。为什么初值是 1：当前格子自己就贡献一个面积单位，四个方向的返回值是它「带来的」额外面积。

以下面这张 3 × 3 网格走一遍：

第 0 行 1 1 0，第 1 行 0 1 0，第 2 行 1 0 1。

(0,0) 是陆地，调用 dfs(0,0)。置 grid[0][0] = 0，answer = 1。向上越界跳过；向右到 (0,1) 是陆地，递归进去：置 grid[0][1] = 0，它自己的 answer = 1，向左回到 (0,0) 已是 0 返回 0（这一步正是「先置 0」在起作用，否则会来回弹跳），向右 (0,2) 是海水返回 0，向下 (1,1) 是陆地，再递归：置 grid[1][1] = 0，四邻分别是已淹没的 (0,1)、海水 (1,0)、海水 (1,2)、海水 (2,1)，全部返回 0，于是 dfs(1,1) = 1。回到 (0,1)：1 + 1 = 2。回到 (0,0)：1 + 2 = 3。第一座岛面积 3，answer 更新为 3。

主循环继续。(0,1)、(0,2)、(1,0)、(1,1)、(1,2) 此刻全是 0，dfs 一进门就返回 0，不做任何递归——这就是「淹没」带来的去重效果。

(2,0) 是陆地，dfs 置 0 后四邻全是海水或越界，返回 1，不足以更新最大值。(2,1) 是海水返回 0。(2,2) 是陆地，同样返回 1。

循环结束，返回 3。

若把「置 0」这一步删掉：dfs(0,0) 会走到 (0,1)，(0,1) 又走回 (0,0)，两者无限互相调用，立刻栈溢出——这是本题最经典的崩溃方式。

代码实现

class Solution {
    private int m;
    private int n;
    private int[][] grid;

    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        int answer = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                answer = Math.max(answer, dfs(i, j));
            }
        }
        return answer;
    }

    private int dfs(int i, int j) {
        // 海水或已被淹没的陆地，贡献 0 个格子。
        if (grid[i][j] == 0) {
            return 0;
        }
        int answer = 1;
        // 必须在递归之前淹没自己，否则邻居会走回来造成无限递归。
        grid[i][j] = 0;
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n) {
                answer += dfs(x, y);
            }
        }
        return answer;
    }
}

func maxAreaOfIsland(grid [][]int) (answer int) {
    m, n := len(grid), len(grid[0])
    dirs := [5]int{-1, 0, 1, 0, -1}
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        // 海水或已被淹没的陆地，贡献 0 个格子。
        if grid[i][j] == 0 {
            return 0
        }
        answer := 1
        // 必须在递归之前淹没自己，否则邻居会走回来造成无限递归。
        grid[i][j] = 0
        for k := 0; k < 4; k++ {
            x, y := i+dirs[k], j+dirs[k+1]
            if x >= 0 && x < m && y >= 0 && y < n {
                answer += dfs(x, y)
            }
        }
        return answer
    }
    for i := range grid {
        for j := range grid[i] {
            answer = max(answer, dfs(i, j))
        }
    }
    return
}

复杂度分析

时间复杂度：$O(mn)$。凭什么：每个格子最多被置 0 一次，此后所有到达它的调用都在第一行返回；主循环 $mn$ 次调用加上递归中每个格子常数次（四个方向）的邻居访问，总量与格子数成正比。

空间复杂度：$O(mn)$。凭什么：没有额外的 visited 数组，唯一的开销是递归栈；最坏情况是整张网格连成一条蛇形的岛，递归深度达到 $mn$。若换成显式栈的迭代写法或 BFS，峰值仍是同一量级。

关键点总结

网格连通块题的第一步是建模成图：格子是点、四邻是边，问题随即变成「最大连通分量的大小」，后面所有写法都是这句话的实现细节。

「先标记再递归」是所有 DFS 洪水填充的铁律；标记晚一步就会在相邻两格之间来回弹跳导致栈溢出，这条比任何优化都重要。

就地把 1 改成 0 当访问标记，省掉 visited 数组，但破坏了入参；面试时要主动说明这个副作用并给出「改用 visited」的替代方案，这体现工程意识。

方向数组 {-1, 0, 1, 0, -1} 的滑动窗口写法能压掉四段重复分支，且天然只覆盖四方向；改成八方向时对应的是另一组偏移，不要混用。

让递归函数返回「本次搜索覆盖的格子数」，比用全局变量累加更容易保证正确性——每一层的语义自洽，也便于口头向面试官解释。

面试视角：本题的 BFS 写法（队列 + 入队时标记）与 DFS 等价，递归深度可能达到 2500，若网格规模再放大，主动提出改用 BFS 规避栈溢出是加分项。

易错点总结

递归之前忘记置 0：grid = [[1,1]] 时 (0,0) 与 (0,1) 互相递归，立刻 StackOverflowError（Go 是 goroutine stack exceeded）。

只在主循环判陆地却不在 dfs 入口判：grid = [[1,0],[0,0]] 时递归会把海水格也计成面积，(0,0) 返回 3 而不是 1。

按八方向搜索：grid = [[1,0],[0,1]] 中两个对角的陆地会被并成一座岛，返回 2 而正确答案是 1。

越界判断漏掉某一侧：只写 x < m && y < n 而漏掉 x >= 0，grid = [[1]] 在向上探测时访问 grid[-1][0]，Java 抛越界异常、Go panic。

answer 初值写成 1 而不是 0：grid = [[0,0],[0,0]] 会返回 1，而全是海水时正确答案是 0。

dfs 里 answer 初值写成 0：grid = [[1]] 返回 0，当前格子自己没有被计入面积，所有答案都会偏小。

用全局变量累加面积却忘了在每座岛之间清零：grid = [[1,0,1]] 会把两座岛的面积累加成 2，而正确答案是 1。

n = grid[0].length 之前没考虑空网格：若测试数据可能给出 grid = []，这一行会直接越界；题目保证 m ≥ 1 才可以这样写，换到不保证的场景要先判空。

主循环里对已淹没的格子额外加 if (grid[i][j] == 1) 之外还重复置 0：grid = [[1,1]] 会在主循环里提前把 (0,1) 抹掉，导致岛被切开，返回 1 而不是 2。

相似题目

题目	难度	考察点
695. 岛屿的最大面积	中等	与本题同题，可直接套用同一份代码
200. 岛屿数量	中等	只数连通块个数不求大小，`dfs` 无需返回值，主循环改成计数
463. 岛屿的周长	简单	统计的是陆地与海水/边界的交界数，遇到越界与海水时要 `+1` 而非返回 0
1020. 飞地的数量	中等	先从边界出发淹掉所有能出海的陆地，再统计剩余格子，是反向染色
130. 被围绕的区域	中等	同样从边界反向染色，但要就地改写字符并做两次遍历还原
1254. 统计封闭岛屿的数目	中等	0 表示陆地，且要判断整座岛是否触碰边界，递归需带回布尔标志
694. 不同岛屿的数量	中等	需要把搜索路径序列化成形状签名去重，考察的是如何刻画连通块的形状
面试题 16.19. 水域大小	中等	八方向连通，且要返回所有水域大小并排序，方向数组要换成八组偏移