LeetCode LCR 105. 岛屿的最大面积

约 6 分钟
文章信息 5 个分类 6 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 深度优先搜索 广度优先搜索 LCR 矩阵 并查集

题目描述

✅ LCR 105. 岛屿的最大面积

image-20260929004451898

image-20260929004451900

题意分析

网格中的 1 表示陆地，只有上下左右相邻的陆地才属于同一座岛。岛屿面积就是它包含的陆地格数，要求返回最大面积，没有陆地时返回 0。

把陆地格看成节点、四方向相邻关系看成边，岛屿就是连通分量。对每个尚未访问的分量搜索一次，统计格数并取最大值即可。

解法：DFS 淹没并统计岛面积

核心思路

[!blue]

dfs(i,j) 返回从当前位置出发，本次搜索新访问的陆地格数。调用前保证坐标合法；若格子是 0，它是海水或已经统计过的陆地，直接贡献 0。

遇到 1 时，先把当前格改为 0，并把局部面积初始化为 1，再递归搜索四个合法邻居，累加它们返回的新增面积。必须先标记再递归，否则相邻陆地会互相走回，重复统计甚至无法终止。

四方向搜索会到达同一座岛的所有陆地，却无法跨过海水到其他岛。每个陆地格在首次进入时就被标记，其他分支再次遇到它只返回 0，因此每个格子恰好计入一次，递归总和就是该岛面积。

外层遍历全部格子，取每次 dfs 返回值的最大值。一座岛第一次被访问时已经全部标记，后续从其中其他位置发起的调用都返回 0。答案从零开始，所以全海水时自然返回零。代码直接修改 grid 作为访问标记，搜索结束后已访问陆地会变成 0。

解题步骤

  1. 保存网格行列数，将最大面积初始化为 0。
  2. 枚举每个格子，调用 dfs 并用返回面积更新最大值。
  3. 递归遇到 0 返回零；遇到陆地则先置零，计入当前格贡献的一。
  4. 用方向数组相邻两项表示上下左右偏移，先检查邻居坐标，再递归累加面积。
  5. 返回本次面积；外层扫描结束后返回最大面积。单行、单列也由相同的边界判断处理。

代码实现

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];
            int 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)$。外层扫描全部格子，每块陆地只展开一次，每次只检查四个邻居；海水或已访问位置立即返回。
  • 空间复杂度：$O(mn)$。最坏情况下，一条搜索路径经过所有陆地，递归深度可达到网格总格数；方向信息只占每层常数空间。

关键点总结

[!green]

  • 一座岛对应一个四连通分量，面积统计完成后再与全局最大值比较。
  • 进入陆地后立即标记，使递归分支的新增计数互不重复。
  • 当前格自己贡献一，邻居返回的是额外找到的陆地数。
  • 用原网格记录访问状态会修改输入，但不需要额外访问矩阵。

易错点总结

[!yellow]

  • 递归邻居后才标记当前格，会让相邻陆地反复走回。
  • 把斜对角也当作邻居，会合并本来不同的岛屿。
  • 只累加邻居却忘记当前格的一，会把面积算小。
  • 把所有岛的面积持续累加到一个全局计数，得到的是总陆地数而不是最大单岛面积。
  • 当前实现只在调用邻居前检查坐标，不能把越界位置直接传给 dfs。

相似题目

题目 难度 关联与区别
200. 岛屿数量 中等 同样寻找四连通分量，原题只累计岛屿个数，本题累计每块面积并取最大。
827. 最大人工岛 困难 在岛屿面积基础上允许翻转一个0，需要合并相邻不同分量的面积并避免重复计入。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/36146417
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！