LeetCode 695. 岛屿的最大面积

◎

本节目标

用 DFS 汇总每个四连通陆地区域的面积并取最大值。

这道题承接网格与状态图搜索的连通块模型：外层枚举每块新陆地，内层 DFS 计算这一个连通块包含多少格。

查看 LeetCode 原题

朴素思路与瓶颈

若从每个陆地格都重新搜索一次，会反复遍历同一座岛。正确做法是首次遇到陆地时完整吞掉这座岛，以后外层扫描到其中任何格子都不会再次启动搜索。

DFS 返回值不变量

dfs(row, col) 的返回值表示“包含当前格的、尚未计数的连通块面积”。越界和水域返回 0；合法陆地先沉为水，贡献 1，再加上四个方向的返回值。

沉岛是永久访问：一个陆地格只能属于一个岛，递归返回后不能恢复为 1。外层在每次 DFS 后用返回值更新全局最大面积。

原地修改

实现会把已访问的陆地从 1 改为 0，因此调用结束后的 grid 不再保留原始岛屿分布。这一修改同时省去了额外访问矩阵，并保证不会重复统计。

代码实现

C++17 与 Python 3 都以 maxAreaOfIsland 作为平台方法，DFS 只处理已传入的网格参数，不读取输入流。

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
private:
    int rows = 0;
    int cols = 0;

    int dfs(vector<vector<int>>& grid, int row, int col) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return 0;
        }
        if (grid[row][col] == 0) {
            return 0;
        }

        // 陆地沉为水后不恢复，每格只属于一个连通块。
        grid[row][col] = 0;
        return 1 + dfs(grid, row - 1, col) + dfs(grid, row + 1, col) +
            dfs(grid, row, col - 1) + dfs(grid, row, col + 1);
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        rows = static_cast<int>(grid.size());
        cols = static_cast<int>(grid[0].size());
        int best = 0;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == 1) {
                    best = max(best, dfs(grid, row, col));
                }
            }
        }
        return best;
    }
};

Python

Python 3

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        def island_area(start_row: int, start_col: int) -> int:
            stack = [(start_row, start_col)]
            grid[start_row][start_col] = 0
            area = 0

            while stack:
                row, col = stack.pop()
                area += 1
                for row_change, col_change in (
                    (-1, 0),
                    (1, 0),
                    (0, -1),
                    (0, 1),
                ):
                    next_row = row + row_change
                    next_col = col + col_change
                    if (
                        0 <= next_row < rows
                        and 0 <= next_col < cols
                        and grid[next_row][next_col] == 1
                    ):
                        # 入栈前沉岛，每格只计入一个连通块。
                        grid[next_row][next_col] = 0
                        stack.append((next_row, next_col))
            return area

        best = 0
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 1:
                    best = max(best, island_area(row, col))
        return best

复杂度分析

设网格大小为 m × n。每个格子至多被 DFS 访问一次，时间复杂度为 O(mn)；最坏情况下递归栈为 O(mn)。原地标记后，除递归栈外的额外空间为 O(1)。

易错点

• 只计算从第一个陆地出发的面积，遗漏其他岛屿。
• 递归返回后恢复陆地，导致同一座岛被多次计数。
• 将对角线也当作相连；本题只有上下左右相连。
• 把水域错误记作面积 1，使全水网格不能返回 0。

模式迁移

只要目标是统计连通分量的大小、数量或边界，就可以让 DFS 返回局部贡献并在外层聚合。需要保留原网格时，改用独立访问矩阵，返回值结构不变。