695. 岛屿的最大面积（Max Area of Island）

频次 ★★★★ · 难度 🟡 · 高频：字节/阿里

题目

m×n 网格，1 是陆地、0 是水，求最大岛屿面积（四联通的 1 的个数）。

示例：

输入:
[[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

思路

DFS 沉没法：遍历网格，每遇到一个 1，启动 DFS 计算该岛屿面积（沉没过程中计数），更新全局 max。

与 200. 岛屿数量唯一区别：200 只计数岛屿个数，695 要记录每个岛屿的面积。

代码

public int maxAreaOfIsland(int[][] grid) {
    int max = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1) {
                max = Math.max(max, dfs(grid, i, j));
            }
        }
    }
    return max;
}
 
private int dfs(int[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0)
        return 0;
    grid[i][j] = 0;                              // 沉没
    return 1 + dfs(grid, i + 1, j)
             + dfs(grid, i - 1, j)
             + dfs(grid, i, j + 1)
             + dfs(grid, i, j - 1);
}

复杂度

• 时间：O(m × n)，每个格子至多访问一次
• 空间：O(m × n) 最坏递归栈深

边界条件

• 空网格：返回 0
• 全 0：返回 0
• 全 1：返回 m×n

变式

• 200. 岛屿数量：只计数岛屿个数，不关心面积
• 827. 最大人工岛：可以填一个 0 变成 1，求最大岛屿面积

易错点

• DFS 返回值设计：沉没当前格子后返回 1 + 四个方向的面积和
• 沉没后不需要恢复（和回溯不同）——这是永久标记
• 输入是 int[][] 不是 char[][]，比较时用 1 和 0

面试追问

• BFS 怎么写？ 用队列，每遇到 1 就 BFS 四方向扩散，同时计数面积
• 和 200 题的区别？ 200 只计数岛屿个数，DFS 返回 void；695 需要返回面积，DFS 返回 int

关联题

• 同套路：200. 岛屿数量 —— 计数版
• 进阶：827. 最大人工岛 —— 填海造岛
• 知识点：网格 DFS 模板（面积版）见图