695. 岛屿的最大面积

🎯 问题描述

给定一个包含 0 和 1 的二维网格 grid，其中 1 代表陆地，0 代表水域。岛屿是由水平方向或垂直方向上相邻的陆地连接而成的。请计算并返回最大的岛屿面积。如果不存在岛屿，则返回面积 0。

测试用例格式：

  • 输入：二维列表 grid，每个元素为 0 或 1
  • 输出：整数，表示最大岛屿面积

💻 解题思路

核心算法：深度优先搜索（DFS）

算法原理

  1. 遍历网格：使用双重循环遍历网格中的每个格子
  2. 发现陆地：当遇到值为 1 的格子时，启动 DFS 计算该岛屿的面积
  3. 淹没岛屿：在 DFS 过程中将访问过的陆地标记为 0，防止重复计算
  4. 面积累加：通过递归返回值累加每个连通陆地的面积

关键技术点

  • 递归返回值：利用返回值传递子问题的解，避免传值问题
  • 边界处理：在递归开始时检查边界条件
  • 状态标记：直接修改原数组标记已访问位置，节省空间

💻 解题思路

思路1： DFS

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        
        n, m = len(grid), len(grid[0])
        max_area = 0
        
        def dfs(i, j):
            # 边界检查和终止条件
            if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] != 1:
                return 0
            
            # 标记为已访问
            grid[i][j] = 0
            
            # 递归计算当前岛屿面积：当前格子(1) + 四个方向的面积
            return 1 + dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1)
        
        # 遍历整个网格
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    # 计算当前岛屿面积并更新最大值
                    current_area = dfs(i, j)
                    max_area = max(max_area, current_area)
        
        return max_area

思路1：📊 性能分析

提交结果
  • 运行时间：19ms击败57.37%
  • 内存消耗：20.32MB击败42.89%
复杂度验证
指标 复杂度 说明
时间复杂度 O(M × N) M 和 N 分别是网格的行数和列数。每个格子最多被访问一次
空间复杂度 O(M × N) 递归调用栈的深度，在最坏情况下（整个网格是一个大岛屿）达到 M×N

思考

⚠️ 常见错误分析

  • 错误1：返回值类型错误
1
2
3
4
# 错误写法
if ...:
    return  # 返回None
return 1 + dfs(...)  # 1 + None 会报错
  • 错误2：参数传递问题
1
2
3
# 错误写法
def dfs(i, j, area):
    area += 1  # 局部变量修改不影响外部

本题是经典的图遍历问题，通过深度优先搜索（DFS）或广度优先搜索（BFS）均可解决。关键在于：

  • 正确处理边界条件
  • 使用返回值累加面积
  • 及时标记已访问节点
  • 比较并更新最大面积