#695 / LCR 105. 岛屿的最大面积

• LeetCode：695. 岛屿的最大面积 · LCR 105. 岛屿的最大面积
• 难度：中等
• 归类：图论、矩阵、深度优先搜索、广度优先搜索、连通分量
• 主解法：DFS + 原地标记

#先给结论

把矩阵中的每个陆地格子看成图的节点，上、下、左、右相邻的陆地之间存在边。一座岛屿就是一个由 1 组成的四方向连通分量，岛屿面积就是该连通分量包含的节点数。

遍历整个网格。每当遇到尚未访问的陆地，就从它出发做一次 DFS：

1. 将当前格子标记为已访问；
2. 当前格子贡献面积 1；
3. 递归统计四个方向相邻陆地的面积；
4. 将本次 DFS 的总面积更新到最大值。

每个格子最多被访问一次，因此时间复杂度为 O(rows × cols)。

#题目描述

给定一个由 0 和 1 组成的二维网格：

• 0 表示水域；
• 1 表示陆地；
• 上、下、左、右相邻的陆地属于同一座岛屿；
• 对角线相邻不算连通。

返回面积最大的岛屿；如果网格中没有陆地，返回 0。

示例：

输入：
grid = [
  [0, 0, 1, 0, 0],
  [1, 1, 1, 0, 1],
  [0, 1, 0, 0, 1],
  [0, 0, 1, 1, 0]
]

输出：5

其中左上区域的岛屿包含 5 个陆地格子：

0 0 ① 0 0
① ① ① 0 1
0 ① 0 0 1
0 0 1 1 0

右上方两个 1 构成面积为 2 的岛屿；右下方两个 1 也构成面积为 2 的岛屿。它们与其他陆地只有对角线接触，因此不能合并。

#问题本质：求最大的连通分量

矩阵可以隐式看成一张图：

格子 grid[row][col] = 1  → 图中的节点
两个陆地格子上下左右相邻 → 节点之间存在边
一座岛屿                → 一个连通分量
岛屿面积                → 连通分量的节点数量

所以问题不是“对每个 1 查看四周”这么简单，而是：

找到所有陆地连通分量，统计每个连通分量的节点数量，并取最大值。

DFS 和 BFS 都能完整遍历一个连通分量。本题不要求最短路径，也不需要按层计算，因此 DFS 通常更简洁；BFS 同样正确。

#DFS 状态与不变量

定义：

dfs(row, col) = 从 grid[row][col] 出发，本次能够访问到的未访问陆地面积

递归过程中保持：

一个陆地格子第一次进入 DFS 时立刻被标记，之后不会再次计数。

这里直接把访问过的陆地从 1 改成 0：

grid[row][col] = 0;

这相当于“淹没”当前陆地。以后从其他方向再次到达它时，会因为它已经是 0 而返回，避免环形相邻关系造成重复计数和无限递归。

#递归的出口与转移

#出口：当前位置不能贡献面积

下面三种情况都返回 0：

1. 行下标越界；
2. 列下标越界；
3. 当前格子是水域或已经访问过。

if (
    row < 0 ||
    row >= rows ||
    col < 0 ||
    col >= cols ||
    grid[row][col] === 0
) {
    return 0;
}

#转移：当前面积加四个方向

合法的未访问陆地先贡献 1，然后递归统计四个方向：

area(row, col)
= 1
+ area(row - 1, col)
+ area(row + 1, col)
+ area(row, col - 1)
+ area(row, col + 1)

#逐步推演

使用一个较小的网格：

grid = [
  [1, 1, 0],
  [0, 1, 0],
  [1, 0, 1]
]

外层遍历首先在 (0, 0) 遇到陆地，开始 DFS。

#第 1 步：访问 (0, 0)

当前格子：(0, 0)
当前贡献：1

访问前：       标记后：
1 1 0          0 1 0
0 1 0    →     0 1 0
1 0 1          1 0 1

四个方向中，只有右侧 (0, 1) 是未访问陆地。

#第 2 步：访问 (0, 1)

0 1 0          0 0 0
0 1 0    →     0 1 0
1 0 1          1 0 1

它的下方 (1, 1) 是未访问陆地。

#第 3 步：访问 (1, 1)

0 0 0          0 0 0
0 1 0    →     0 0 0
1 0 1          1 0 1

四个方向都没有新的陆地，递归开始返回：

dfs(1, 1) = 1
dfs(0, 1) = 1 + dfs(1, 1) = 2
dfs(0, 0) = 1 + dfs(0, 1) = 3

第一座岛屿面积为 3，此时 maxArea = 3。

#继续扫描剩余网格

0 0 0
0 0 0
1 0 1

(2, 0) 和 (2, 2) 分别是面积为 1 的岛屿。注意它们之间隔着水域，且即使仅对角线相邻也不能连通。

最终最大面积仍为 3。

#代码实现

#JavaScript：DFS 原地标记

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function (grid) {
    if (grid.length === 0 || grid[0].length === 0) {
        return 0;
    }

    const rows = grid.length;
    const cols = grid[0].length;
    let maxArea = 0;

    // 返回从 (row, col) 出发能够找到的未访问陆地面积
    const dfs = (row, col) => {
        // 越界、水域和已经访问过的陆地都不贡献面积
        if (
            row < 0 ||
            row >= rows ||
            col < 0 ||
            col >= cols ||
            grid[row][col] === 0
        ) {
            return 0;
        }

        // 进入格子时立即标记，防止它从其他方向被重复访问
        grid[row][col] = 0;

        // 当前格子贡献 1，再累加四个方向的连通陆地面积
        return (
            1 +
            dfs(row - 1, col) +
            dfs(row + 1, col) +
            dfs(row, col - 1) +
            dfs(row, col + 1)
        );
    };

    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            // 水域和已被其他 DFS 淹没的陆地会得到面积 0
            maxArea = Math.max(maxArea, dfs(row, col));
        }
    }

    return maxArea;
};

#代码与思路对照

#正确性证明

#一次 DFS 得到一座完整岛屿的面积

从某个未访问陆地出发，DFS 会沿上、下、左、右访问所有可达陆地，所以同一座岛屿中的每个格子都会被访问。同时，DFS 不会跨过值为 0 的水域，也不会沿对角线移动，因此不会访问其他岛屿。

进入每个陆地格子时立即将它标记为 0，保证它只贡献一次面积。因此一次 DFS 的返回值恰好等于该岛屿的面积。

#外层扫描不会遗漏岛屿

外层循环检查网格中的每个位置。任何岛屿在第一次遇到其某个陆地格子时，都会被一次 DFS 完整访问；之后该岛屿已经全部被标记，不会重复统计。最终 maxArea 是所有岛屿面积中的最大值。

#复杂度分析

设网格有 rows 行、cols 列：

• 时间复杂度：O(rows × cols)。外层扫描每个格子，DFS 中每块陆地最多访问一次；检查四个方向是常数操作。
• 空间复杂度：最坏 O(rows × cols)。当所有格子都是陆地且递归路径很深时，递归调用栈可能包含所有格子。

原地标记本身只使用 O(1) 额外存储，但不能因此忽略递归栈并把整体空间复杂度写成 O(1)。

#替代解法：BFS

如果担心大网格导致递归调用栈溢出，可以使用显式队列遍历一座岛屿：

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function (grid) {
    if (grid.length === 0 || grid[0].length === 0) {
        return 0;
    }

    const rows = grid.length;
    const cols = grid[0].length;
    const directions = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1],
    ];

    let maxArea = 0;

    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (grid[row][col] === 0) {
                continue;
            }

            let area = 0;
            let head = 0;
            const queue = [[row, col]];

            // 入队时立即标记，避免同一格子被多个邻居重复入队
            grid[row][col] = 0;

            while (head < queue.length) {
                const [currentRow, currentCol] = queue[head++];
                area++;

                for (const [rowOffset, colOffset] of directions) {
                    const nextRow = currentRow + rowOffset;
                    const nextCol = currentCol + colOffset;

                    if (
                        nextRow < 0 ||
                        nextRow >= rows ||
                        nextCol < 0 ||
                        nextCol >= cols ||
                        grid[nextRow][nextCol] === 0
                    ) {
                        continue;
                    }

                    // 必须在入队时标记，而不是出队时标记
                    grid[nextRow][nextCol] = 0;
                    queue.push([nextRow, nextCol]);
                }
            }

            maxArea = Math.max(maxArea, area);
        }
    }

    return maxArea;
};

BFS 不需要按层统计，因为题目只关心连通分量包含多少格子，不关心从起点走了多少步。队列中的每个节点出队时令 area++ 即可。

#如果不能修改输入

原地把 1 改成 0 最简单，但会改变调用方传入的 grid。如果接口要求保留输入，可以创建访问数组：

const visited = Array.from(
    { length: rows },
    () => Array(cols).fill(false),
);

之后将判断条件改为：

grid[row][col] === 0 || visited[row][col]

访问陆地时写：

visited[row][col] = true;

两种方案对比：

#DFS、BFS 与并查集对比

本题只需要一次性统计静态网格，DFS 或 BFS 足够。并查集能做，但没有必要增加结构复杂度。

#边界与陷阱

• 全是水域：没有 DFS 能得到正面积，初始答案 0 直接保留。
• 只有一个陆地：DFS 返回 1。
• 对角线相邻：不属于同一岛屿，只能使用四个方向，不能加入斜方向。
• 访问后才标记：DFS 会在相邻格子间来回递归；BFS 会让同一格子重复入队。必须在进入递归或入队时立即标记。
• 每个起点使用新的 visited：会让同一座岛屿被反复遍历，最坏复杂度显著增加；访问状态应在整个扫描过程中共享。
• 使用字符串坐标 Set：${row},${col} 虽然正确，但会创建大量字符串；矩阵原地标记或二维布尔数组通常更直接。
• 使用 queue.shift()：JavaScript 数组头删通常是 O(n)；使用 head 指针模拟出队。
• 忽略输入被修改：原地标记后 grid 不再保持原值，需要按接口约定选择方案。
• 递归过深：大面积细长岛屿可能触发 JavaScript 调用栈限制，可以改用 BFS 或显式栈。

#面试官递进追问

#1. 为什么这道题可以建模为连通分量问题？

每个陆地格子是节点，四方向相邻关系是边，一座岛屿恰好是一组互相可达的节点。因此面积就是连通分量的节点数。

为什么问： 检查能否从矩阵表象识别隐式图结构。

#2. dfs(row, col) 的返回值是什么？

它返回从当前位置出发能够遍历到的、尚未访问的四方向连通陆地数量。非法位置和水域返回 0，合法陆地返回 1 加四个方向的结果。

为什么问： 返回值定义决定递归累加是否正确。

#3. 为什么进入陆地后要立刻标记？

网格相邻关系是双向的。如果不立即标记，两个相邻格子会互相再次访问，导致重复计数甚至无限递归。

为什么问： 检查是否理解访问标记维持的不变量。

#4. 为什么对角线不能计入面积？

题目将岛屿定义为水平或垂直方向连通，因此图中只存在四方向边。是否包含对角线由题目定义决定，不是 DFS 自身的限制。

为什么问： 检查是否区分算法能力与问题的邻接规则。

#5. DFS 和 BFS 应该如何选择？

两者时间复杂度相同。递归 DFS 更简洁；BFS 使用显式队列，能够避免语言调用栈深度限制。这里不需要 BFS 分层，因为面积与距离无关。

为什么问： 检查能否根据工程限制取舍，而不是机械套模板。

#6. 原地标记的空间复杂度是不是 O(1)？

访问标记本身是 O(1)，但递归 DFS 还有最坏 O(rows × cols) 的调用栈，因此算法整体空间复杂度不能写成 O(1)。

为什么问： 检查复杂度分析是否遗漏隐式调用栈。

#7. 如果网格不能被修改怎么办？

使用与网格同尺寸的 visited 布尔数组，或复制网格后再原地标记。前者额外空间为 O(rows × cols)。

为什么问： 检查是否关注函数副作用和接口约束。

#8. 如果陆地会不断动态增加，如何维护最大面积？

可以用并查集。每次新增陆地时，将它与四周已有陆地合并，并维护每个连通分量的大小和全局最大值。

为什么问： 检查能否将静态遍历迁移到动态连通场景。

#常见错误回答

• “用 BFS，因为要按层”：本题不求最短距离，BFS 无需分层；DFS 也同样适用。
• “遇到 1 就把答案加一”：这只能统计陆地总数，不能区分不同岛屿并取最大面积。
• “辅助空间是 O(1)”：忽略了 DFS 调用栈或 BFS 队列。
• “八个方向都搜索”：改变了题目的连通定义，会错误合并仅对角线接触的岛屿。
• 每次 DFS 都新建访问集合：没有让外层扫描共享访问状态，会重复遍历已经计算过的岛屿。

#可迁移总结

• 核心关键词：隐式图、四方向连通、连通分量、访问标记、面积累加。
• 一句话本质：遍历所有陆地连通分量，统计每个分量的节点数并取最大值。
• 因果链：扫描网格 → 发现未访问陆地 → DFS/BFS 淹没整座岛屿 → 得到面积 → 更新最大值。
• 可以迁移到岛屿数量、被围绕的区域、飞地数量、最大人工岛和图的连通分量问题。
• 1 分钟回答：说明图建模、DFS 返回值和 O(rows × cols) 复杂度。
• 3 分钟回答：补充原地标记不变量、四方向定义和示例推演。
• 10 分钟回答：写出代码与证明，并比较 DFS、BFS、并查集及不修改输入的方案。

#刷题后自测

1. 为什么一次 DFS 的返回值恰好是一座岛屿的面积？
2. 如果把 grid[row][col] = 0 放到四次递归之后，会发生什么？
3. 为什么 BFS 版本不需要固定每层队列长度？
4. 只在对角线上接触的两个陆地为什么不属于同一座岛屿？
5. 如果网格会动态加入陆地，为什么并查集比每次重新 DFS 更合适？