树与图中等1 种解法

#695岛屿的最大面积

在 0/1 网格中按上下左右连接陆地，返回最大岛屿包含的格子数。

#矩阵#深度优先搜索#网格

解题主线

遇到未访问陆地就启动 DFS，当前格面积等于 1 加四个方向返回的面积。

把访问过的 1 改为 2，可同时充当 visited 集合并避免重复计数。

遍历所有格子并取每次 DFS 面积最大值，即可覆盖所有连通分量。

解法 1：原地标记深度优先搜索

扫描每个陆地起点，递归累加四邻域面积，并将访问过的陆地标为 2。

时间复杂度

O(mn)

空间复杂度

O(mn) 最坏，来自递归栈

695. 岛屿的最大面积 · 原地标记深度优先搜索

java

final class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

        int maximumArea = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[0].length; column++) {
                if (grid[row][column] == 1) {
                    maximumArea = Math.max(maximumArea, area(grid, row, column));
                }
            }
        }
        return maximumArea;
    }

    private int area(int[][] grid, int row, int column) {
        if (row < 0 || row >= grid.length || column < 0 || column >= grid[0].length) {
            return 0;
        }
        if (grid[row][column] != 1) return 0;

        grid[row][column] = 2;
        return 1
            + area(grid, row - 1, column)
            + area(grid, row + 1, column)
            + area(grid, row, column - 1)
            + area(grid, row, column + 1);
    }
}

扫描每个陆地起点，递归累加四邻域面积，并将访问过的陆地标为 2。

边界与易错点

连接只包含上下左右，不包含对角线。
原地标记会修改输入网格；若需复用输入，应先复制或另建 visited。
大而细长的岛屿可能导致递归栈很深，工程场景可改用显式栈。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q_island_maxArea_695.java