LeetCode LCR 105. 岛屿的最大面积

Categories:

题目描述
思路分析
1. 解法一：DFS 沉岛（推荐）
相似题目

题目描述

✅ LCR 105. 岛屿的最大面积

思路分析

解法一：DFS 沉岛（推荐）

核心思路：

遍历矩阵每个格子，遇到陆地（值为 1）时启动 DFS，计算该岛屿面积，并更新最大值。

沉岛技巧：DFS 时将访问过的陆地格子置为 0（标记已访问），避免重复计数，无需额外 visited 数组。

DFS 返回值：当前格面积（1）+ 四个方向子格的面积之和；越界或为水域则返回 0。

推导：与 [200. 岛屿数量] 的区别在于，岛屿数量只计连通分量个数，本题需累计面积，用递归返回值自然汇总。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 为矩阵行列数，每个格子最多访问一次

空间复杂度：O(m × n)，递归栈深度最坏等于格子总数

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == 1) {
                    maxArea = Math.max(maxArea, dfs(grid, r, c));
                }
            }
        }
        return maxArea;
    }

    private int dfs(int[][] grid, int r, int c) {
        // 越界或为水域，面积为 0
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) {
            return 0;
        }
        // 标记为已访问（沉岛）
        grid[r][c] = 0;
        // 当前格面积 1 + 四方向递归面积
        return 1 + dfs(grid, r + 1, c) + dfs(grid, r - 1, c)
                + dfs(grid, r, c + 1) + dfs(grid, r, c - 1);
    }
}

func maxAreaOfIsland(grid [][]int) int {
	row, col := len(grid), len(grid[0])
	maxArea := 0

	var dfs func(r, c int) int
	dfs = func(r, c int) int {
		// 越界或为水域，面积为 0
		if r < 0 || r >= row || c < 0 || c >= col || grid[r][c] == 0 {
			return 0
		}
		// 标记为已访问（沉岛）
		grid[r][c] = 0
		// 当前格面积 1 + 四方向递归面积
		return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
	}

	for r := 0; r < row; r++ {
		for c := 0; c < col; c++ {
			if grid[r][c] == 1 {
				maxArea = max(maxArea, dfs(r, c))
			}
		}
	}
	return maxArea
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS 连通分量计数
463. 岛屿的周长	简单	DFS 边界计算
827. 最大人工岛	困难	DFS 岛屿标记+合并
130. 被围绕的区域	中等	DFS 从边界反向标记
417. 太平洋大西洋水流问题	中等	多源 DFS/BFS
1020. 飞地的数量	中等	DFS 从边界消除

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/36146417