岛屿的最大面积

这是一道围绕算法展开的高频练习。建议先掌握「DFS 洪泛」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

算法

题目分析

这道题表面上是在处理「岛屿的最大面积」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考算法这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：把每一块陆地看成一个连通块，遇到陆地就做 DFS，把整块岛屿面积一次性算出来。

推荐代码

推荐解法：DFS 洪泛

时间复杂度： O(mn)

空间复杂度： O(mn)

核心思路：把每一块陆地看成一个连通块，遇到陆地就做 DFS，把整块岛屿面积一次性算出来。

class Solution {
    private static final int[][] DIRECTIONS = {
        {1, 0}, {-1, 0}, {0, 1}, {0, -1}
    };

    public int maxAreaOfIsland(int[][] grid) {
        int best = 0;

        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                if (grid[row][col] == 1) {
                    best = Math.max(best, dfs(grid, row, col));
                }
            }
        }

        return best;
    }

    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;
        int area = 1;

        for (int[] direction : DIRECTIONS) {
            area += dfs(grid, row + direction[0], col + direction[1]);
        }

        return area;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会把每个岛屿看成网格里的一个连通块，用 DFS 统计面积。

核心过程

先遍历整个网格。
遇到一个陆地格子，就启动一次 DFS。
DFS 会把这一整块岛屿全部走完，并返回面积。
每次更新最大面积即可。

复杂度总结

时间复杂度 O(mn)，空间复杂度 O(mn)。

面试补一句：这题最核心的是“每个陆地格子只进 DFS 一次”。

核心思路

题目本质是在网格里找 4 连通分量的最大大小。每次从一个未访问的陆地出发做 DFS，就能统计这一整块岛屿的面积。

步骤讲解

逐格扫描网格

遇到值为 1 的陆地，就把它当成一个新岛屿的起点。

为什么这样做：只有从未处理的陆地出发，才有必要扩展连通块。

对应代码提示：if (grid[row][col] == 1) { ... }

DFS 扩展整块岛屿

向上下左右递归，累计面积并把访问过的陆地标记掉。

为什么这样做：这样同一块岛屿只会统计一次。

对应代码提示：grid[row][col] = 0;

维护最大面积

每次 DFS 返回当前岛屿面积，拿它更新全局最大值。

为什么这样做：题目只关心面积最大的那一块。

对应代码提示：best = Math.max(best, dfs(...));

易错点

访问过的陆地没有及时标记

会导致重复统计，甚至在 DFS 中来回递归死循环。

正确理解：进入 DFS 后第一时间把当前格子置为 0 或单独打 visited 标记。

边界条件判断不完整

越界、水域、已访问格子都应该立即停止扩展。

正确理解：把三种停止条件统一写在 DFS 开头。

复杂度与适用判断

时间复杂度：O(mn)

空间复杂度：O(mn)

比其他方案更好在哪里：比从每个格子重复搜索要高效得多。

适用判断：网格题里一看到“岛屿”“连通块”“面积/数量”，基本就该想到 DFS 或 BFS 洪泛。

额外提醒

扫描负责发现新岛屿，DFS 负责一次性吞掉整块连通区域。