树与图中等1 种解法
#695岛屿的最大面积
在 0/1 网格中按上下左右连接陆地，返回最大岛屿包含的格子数。
#矩阵#深度优先搜索#网格
原题
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例 1：
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] 输出：6 解释：答案不应该是11，因为岛屿只能包含水平或垂直这四个方向上的1。
示例 2：
输入：grid = [[0,0,0,0,0,0,0,0]] 输出：0
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]为0或1
解题主线
- 遇到未访问陆地就启动 DFS，当前格面积等于 1 加四个方向返回的面积。
- 把访问过的 1 改为 2，可同时充当 visited 集合并避免重复计数。
- 遍历所有格子并取每次 DFS 面积最大值，即可覆盖所有连通分量。
解法 1：原地标记深度优先搜索
扫描每个陆地起点，递归累加四邻域面积，并将访问过的陆地标为 2。
-
时间复杂度： O(mn)
-
空间复杂度： O(mn) 最坏，来自递归栈
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);
}
}边界与易错点
- 连接只包含上下左右，不包含对角线。
- 原地标记会修改输入网格；若需复用输入，应先复制或另建 visited。
- 大而细长的岛屿可能导致递归栈很深，工程场景可改用显式栈。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/medium/Q_island_maxArea_695.java