LeetCode 695. 岛屿的最大面积

约 6 分钟
文章信息 22 个分类 5 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 历史考题 50-100 腾讯 字节 阿里 华为 微软 美团 拼多多 京东 小米 百度 网易 快手 B站 商汤 猿辅导
标签
数组 深度优先搜索 广度优先搜索 矩阵 并查集

题目描述

✅ 695. 岛屿的最大面积

:::fold 历史考题

考察公司：小米
考察日期：2025.5.23

:::

image-20260928195418066

image-20260928195418068

image-20260928195418069

题意分析

网格中 1 表示陆地，0 表示水。只有上下左右相邻的陆地才属于同一座岛屿，斜对角接触不算连通。岛屿面积是其中陆地格子的数量，要求返回面积最大的岛屿，而不是把所有岛屿面积相加。

需要先确定每个连通块包含哪些陆地，再分别统计面积。一次搜索可能从不同路线到达同一格，因此必须记录是否访问过。下面直接把已经统计的陆地改为 0，避免额外的访问数组，但会修改原网格；全是水时返回 0。

解法：DFS 淹没已访问陆地

核心思路

[!blue]

外层按行、列扫描整个网格。遇到仍为 1 的格子，说明找到了一座尚未统计的岛屿，从这里启动深度优先搜索，沿四个方向把与它连通的陆地全部找出来，用本次搜索的面积更新最大值。

在 DFS 中，越界或遇到水域就返回 0，表示这条路线没有新增陆地。遇到陆地时，先把它改为水，计入当前格子的 1，再递归搜索上、下、左、右四个邻居，把各方向新发现的面积累加。

标记必须发生在搜索邻居之前。相邻格子可能再走回当前格，不同方向也可能绕行到同一块陆地；提前改为水后，这些再次到达都会立即返回 0。各分支统计的是自己新发现的格子，已经被前一个分支处理过的部分不会再次计数。

只要某块陆地属于当前岛屿，就存在一条四方向陆地路径可以从入口到达它；搜索会沿这些邻接关系扩展，因此不会漏掉岛内格子，也不会越过水域进入另一座岛。每块新陆地又只贡献一次 1，所以本次最外层 DFS 的返回值恰好是这座岛的面积。

搜索完成后，整座岛已经被标记为水。外层扫描之后再经过这些位置时会直接跳过，直到找到下一座岛；只对各次搜索结果取最大值，才能得到最大岛屿面积。

解题步骤

  1. 初始化最大面积 ans = 0，逐行扫描所有格子。
  2. 仅在当前格仍为陆地时调用 DFS，开始统计一座新岛。
  3. DFS 先检查行列边界，再检查格子是否为水；无新增陆地则返回 0。
  4. 把当前陆地改为水，返回当前格的 1 加上四个方向递归得到的新增面积。
  5. 用每座岛的面积更新 ans，全部扫描结束后返回它。

代码实现

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    ans = Math.max(ans, dfs(grid, i, j));
                }
            }
        }

        return ans;
    }

    private int dfs(int[][] grid, int row, int col) {
        if (row < 0
                || row >= grid.length
                || col < 0
                || col >= grid[0].length
                || grid[row][col] == 0) {
            return 0;
        }

        // 先标记本格，其他路线再次到达时就不会重复计入面积。
        grid[row][col] = 0;

        return 1
                + dfs(grid, row - 1, col)
                + dfs(grid, row + 1, col)
                + dfs(grid, row, col - 1)
                + dfs(grid, row, col + 1);
    }
}

func maxAreaOfIsland(grid [][]int) int {
    ans := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 1 {
                area := dfsIsland(grid, i, j)
                if area > ans {
                    ans = area
                }
            }
        }
    }
    return ans
}

func dfsIsland(grid [][]int, row int, col int) int {
    if row < 0 || row >= len(grid) || col < 0 || col >= len(grid[0]) || grid[row][col] == 0 {
        return 0
    }

    // 先标记本格，其他路线再次到达时就不会重复计入面积。
    grid[row][col] = 0
    return 1 + dfsIsland(grid, row-1, col) + dfsIsland(grid, row+1, col) +
        dfsIsland(grid, row, col-1) + dfsIsland(grid, row, col+1)
}

复杂度分析

  • 时间复杂度：$O(mn)$，外层扫描所有格子，每块陆地只会展开一次，每次展开只检查四个邻居。水域和已访问格子可能被相邻节点再次检查，但这些检查总量仍为线性量级。
  • 空间复杂度：$O(mn)$，虽然不另建访问数组，递归栈仍可能沿一条很长的连通路径包含线性数量的陆地格子。

关键点总结

[!green]

  • 外层遍历寻找岛屿入口，DFS 负责计算一个连通块的面积。
  • 必须先标记当前格子，再递归相邻格子，避免重复访问。
  • 原地标记会修改输入；若输入不可变，需要额外的 visited 集合。
  • 题目只将上下左右相邻的陆地视为同一座岛。

易错点总结

[!yellow]

  • 标记放在递归之后，会导致相邻陆地互相访问并无限递归。
  • 将对角线也加入搜索，会错误合并本不相连的岛屿。
  • 行边界使用 grid.length，列边界应使用 grid[0].length。
  • 全水网格答案为 0，最大面积应从 0 初始化。

相似题目

题目 难度 关联与区别
200. 岛屿数量 中等 同样寻找四连通分量，原题只累计岛屿个数，本题累计每块面积并取最大。
827. 最大人工岛 困难 在岛屿面积基础上允许翻转一个0，需要合并相邻不同分量的面积并避免重复计入。
733. 图像渲染 简单 用洪水填充标记网格连通分量；本题统计各分量面积并取最大，该题修改起点所属的同色分量。
1020. 飞地的数量 中等 用洪水填充标记网格连通分量；本题统计各分量面积并取最大，该题从边界排除可逃离的陆地。
1254. 统计封闭岛屿的数目 中等 用洪水填充标记网格连通分量；本题统计各分量面积并取最大，该题排除接触边界的零分量。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/66529937
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！