LeetCode 695. 岛屿的最大面积

2026-06-23 HGNULB 约 4 分钟

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

分类

LeetCode CodeTop 中等已解决已掌握历史考题 50-100 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度京东华为拼多多网易小米商汤哔哩哔哩

题目描述

✅ 695. 岛屿的最大面积

考察公司：小米

考察日期：2025.5.23

题意分析

给定一个只含 0 和 1 的二维网格，1 是陆地，0 是水域。上下左右相邻的陆地连成一座岛屿，题目要的不是岛屿有几座，而是面积最大的那座岛有多少格陆地——这是它和「岛屿数量」最本质的区别：那题只需要数连通块的个数，这题还要对每个连通块计数，再取最大值。

约束上有两个信号值得注意。其一，相邻只算上下左右四个方向，对角线相接的两块陆地属于不同岛屿；其二，网格规模最多 $50 \times 50$，格子总数很小，说明允许对整张图做完整遍历，甚至递归深度达到全网格也不会有问题。

边界情况：网格中可能一块陆地都没有，此时不存在任何岛屿，题目约定返回 0；也可能整张网格全是陆地，答案就是 $m \times n$。

解法：DFS 淹没已访问陆地

核心思路

遍历网格，每遇到一块未访问的陆地就用 DFS 搜索整座岛，并累计面积。访问陆地时立即将 1 改为 0，让网格本身充当访问标记，保证每个格子最多统计一次。

解题步骤

双层循环扫描每个格子，遇到 1 时启动 DFS。

DFS 遇到越界或水域返回 0。

将当前陆地改为 0，再累加四个方向的面积。

用每次 DFS 的返回值更新最大面积。

代码实现

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)$，最坏情况下递归栈包含全部陆地格子。

关键点总结

外层遍历寻找岛屿入口，DFS 负责计算一个连通块的面积。

必须先标记当前格子，再递归相邻格子，避免重复访问。

原地标记会修改输入；若输入不可变，需要额外的 visited 集合。

题目只将上下左右相邻的陆地视为同一座岛。

易错点总结

标记放在递归之后，会导致相邻陆地互相访问并无限递归。

将对角线也加入搜索，会错误合并本不相连的岛屿。

行边界使用 grid.length，列边界应使用 grid[0].length。

全水网格答案为 0，最大面积应从 0 初始化。

相似题目

题目	难度	考察点
200. 岛屿数量	中等	只数连通块个数，不必计面积
130. 被围绕的区域	中等	反向思维：从边界出发标记不被围的区域
463. 岛屿的周长	简单	度量对象换成周长，统计陆地与水域的邻接边
694. 不同岛屿的数量	中等	在遍历中序列化岛屿形状再去重
1020. 飞地的数量	中等	先淹掉与边界相连的陆地，再统计剩余
1254. 统计封闭岛屿的数目	中等	0/1 语义互换，判定岛屿是否触边
305. 岛屿数量 II	困难	动态加陆地，需改用并查集在线维护
LCR 105. 岛屿的最大面积	中等	本题的 LCR 镜像题，同一套代码
面试题 16.19. 水域大小	中等	求所有连通块面积并排序，且相邻含对角线