当前位置：首页 > news >正文

如何掌握岛屿问题：连通分量计数与面积计算的终极指南

news 2026/5/5 8:14:35

如何掌握岛屿问题：连通分量计数与面积计算的终极指南

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

岛屿问题是算法面试中的经典题型，主要考察对二维网格的遍历和连通区域的处理能力。本文将带你系统学习岛屿数量统计和最大面积计算的核心方法，通过实战案例掌握深度优先搜索（DFS）的应用技巧，让你轻松应对各类岛屿问题变种。

岛屿问题基础：从网格到连通区域

岛屿问题通常以二维网格为背景，其中1代表陆地，0代表水域。核心任务包括：统计独立岛屿的数量、计算最大岛屿面积、判断岛屿周长等。这类问题本质上是连通分量查找的变种，是DFS（深度优先搜索）算法的典型应用场景。

图1：岛屿数量问题中连通区域的可视化表示，红色区域为一个完整岛屿

核心概念解析

连通分量：由相邻（上下左右）陆地组成的区域，斜向相邻不算
边界条件：网格四周均视为水域
原地标记：通过修改原网格值避免额外空间开销（将访问过的陆地标记为水域）

实战一：岛屿数量统计（LeetCode 200）

统计岛屿数量是最基础的岛屿问题，要求计算网格中独立连通的陆地区域个数。

解题思路

遍历整个网格，遇到未访问的陆地（值为1）时：
- 启动DFS遍历整个连通区域
- 将访问过的陆地标记为0（原地修改技巧）
- 岛屿计数器加1
DFS实现要点：
- 检查边界条件（是否越界）
- 检查当前位置是否为陆地
- 递归访问上下左右四个方向

关键代码片段

def numIslands(grid): if not grid: return 0 count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': dfs(grid, i, j) count += 1 return count def dfs(grid, i, j): # 边界条件判断 if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1': return # 原地标记为已访问 grid[i][j] = '0' # 递归访问四个方向 dfs(grid, i+1, j) dfs(grid, i-1, j) dfs(grid, i, j+1) dfs(grid, i, j-1)

完整代码可参考：problems/200.number-of-islands.md

复杂度分析

时间复杂度：O(m×n)，其中m和n分别为网格的行数和列数
空间复杂度：O(m×n)，最坏情况下（全为陆地）递归栈深度达到m×n

实战二：岛屿的最大面积（LeetCode 695）

最大面积问题是岛屿数量统计的延伸，要求计算所有岛屿中面积最大的那个。

解题思路

在基础DFS框架上增加面积计数功能：

每次进入新岛屿时初始化面积为0
DFS过程中每访问一个陆地格子，面积加1
记录并更新最大面积值

核心代码差异

def maxAreaOfIsland(grid): max_area = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == 1: current_area = dfs(grid, i, j) max_area = max(max_area, current_area) return max_area def dfs(grid, i, j): if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != 1: return 0 grid[i][j] = 0 # 标记为已访问 # 累计当前格子面积（1）加上四个方向的面积 return 1 + dfs(grid, i+1, j) + dfs(grid, i-1, j) + dfs(grid, i, j+1) + dfs(grid, i, j-1)

应用场景拓展

最大面积问题的思路可扩展到多种类似场景：

统计湖泊的最大深度
查找油田的最大储量
计算森林中最大树木集群

通用解题模板与优化技巧

标准DFS模板

def dfs(grid, i, j): # 边界条件判断 if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != TARGET: return BASE_CASE # 原地标记 grid[i][j] = VISITED_MARK # 递归处理四个方向 return PROCESS(1, dfs(grid, i+1, j), dfs(grid, i-1, j), dfs(grid, i, j+1), dfs(grid, i, j-1))