LeetCode经典算法面试题 #200：岛屿数量（DFS、并查集等五种实现方案详细解析）

目录

• 1. 问题描述
• 2. 问题分析
• • 2.1 题目理解
  • 2.2 核心洞察
  • 2.3 破题关键
• 3. 算法设计与实现
• • 3.1 深度优先搜索（DFS）递归
  • 3.2 广度优先搜索（BFS）迭代
  • 3.3 并查集（Union-Find）
  • 3.4 DFS迭代（栈实现）
  • 3.5 BFS变体（使用方向数组优化）
• 4. 性能对比
• • 4.1 复杂度对比表
  • 4.2 实际性能测试
  • 4.3 各场景适用性分析
• 5. 扩展与变体
• • 5.1 岛屿的最大面积
  • 5.2 统计封闭岛屿数量
  • 5.3 岛屿的周长
  • 5.4 统计子岛屿数量
• 6. 总结
• • 6.1 核心思想总结
  • 6.2 算法选择指南
  • 6.3 实际应用场景
  • 6.4 面试建议
  • 6.5 常见面试问题Q&A

1. 问题描述

给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出：1

示例 2：

输入：grid = [
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

2. 问题分析

2.1 题目理解

这是一个在二维网格中寻找连通分量的问题。我们可以将网格看作一个图，其中：

• 每个陆地单元格('1')是图中的一个节点
• 相邻的陆地单元格（上下左右四个方向）之间存在边
• 每个岛屿对应图中的一个连通分量

问题的核心是统计网格中连通分量的数量，即寻找所有由'1'组成的连通区域。

2.2 核心洞察

2.3 破题关键

3. 算法设计与实现

3.1 深度优先搜索（DFS）递归

核心思想：

使用递归实现的深度优先搜索，从每个未访问的陆地单元格开始，递归地访问其上下左右相邻的陆地单元格，并将它们标记为已访问。

算法思路：

Java代码实现：

class Solution1 {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int m = grid.length;
int n = grid[0].length;
int count = 0;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}

return count;
}

private void dfs(char[][] grid, int i, int j) {
int m = grid.length;
int n = grid[0].length;

// 边界检查
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
return;
}

// 标记当前单元格为已访问（改为'0'）
grid[i][j] = '0';

// 递归访问四个相邻方向
dfs(grid, i – 1, j); // 上
dfs(grid, i + 1, j); // 下
dfs(grid, i, j – 1); // 左
dfs(grid, i, j + 1); // 右
}
}

性能分析：

• 时间复杂度：O(m×n)，每个单元格最多被访问一次
• 空间复杂度：O(m×n)，最坏情况下递归栈的深度可能达到网格大小（当整个网格都是陆地时）
• 优点：代码简洁，容易理解和实现
• 缺点：递归深度可能很大，对于大网格可能导致栈溢出

3.2 广度优先搜索（BFS）迭代

核心思想：

使用队列实现的广度优先搜索，从每个未访问的陆地单元格开始，将其所有相邻的陆地单元格加入队列，并标记为已访问。

算法思路：

Java代码实现：

import java.util.LinkedList;
import java.util.Queue;

class Solution2 {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int m = grid.length;
int n = grid[0].length;
int count = 0;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
bfs(grid, i, j);
}
}
}

return count;
}

private void bfs(char[][] grid, int i, int j) {
int m = grid.length;
int n = grid[0].length;

// 使用队列进行BFS
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
grid[i][j] = '0'; // 标记为已访问

// 方向数组：上、下、左、右
int[][] directions = {{–1, 0}, {1, 0}, {0, –1}, {0, 1}};

while (!queue.isEmpty()) {
int[] current = queue.poll();
int row = current[0];
int col = current[1];

// 检查四个方向
for (int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];

// 检查边界和单元格状态
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n
&& grid[newRow][newCol] == '1') {
queue.offer(new int[]{newRow, newCol});
grid[newRow][newCol] = '0'; // 标记为已访问
}
}
}
}
}

性能分析：

• 时间复杂度：O(m×n)，每个单元格最多被访问一次
• 空间复杂度：O(min(m, n))，队列的最大长度由网格的宽度或高度决定
• 优点：避免了递归栈溢出的风险，适合大网格
• 缺点：需要额外的队列空间

3.3 并查集（Union-Find）

核心思想：

将每个陆地单元格看作一个独立的集合，遍历网格并将相邻的陆地单元格合并到同一个集合中，最后统计集合的数量。

算法思路：

Java代码实现：

class Solution3 {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int m = grid.length;
int n = grid[0].length;

UnionFind uf = new UnionFind(grid);

// 遍历网格，合并相邻的陆地
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
// 将二维坐标转换为一维索引
int index = i * n + j;

// 检查右侧相邻单元格
if (j + 1 < n && grid[i][j + 1] == '1') {
uf.union(index, i * n + (j + 1));
}

// 检查下侧相邻单元格
if (i + 1 < m && grid[i + 1][j] == '1') {
uf.union(index, (i + 1) * n + j);
}
}
}
}

return uf.getCount();
}

// 并查集实现
class UnionFind {
private int[] parent;
private int[] rank;
private int count; // 岛屿数量

public UnionFind(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
parent = new int[m * n];
rank = new int[m * n];

// 初始化
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
int index = i * n + j;
parent[index] = index;
count++;
}
}
}
}

public int find(int x) {
// 路径压缩
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}

public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);

if (rootX != rootY) {
// 按秩合并
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
count—; // 合并后集合数量减少
}
}

public int getCount() {
return count;
}
}
}

性能分析：

• 时间复杂度：O(m×n×α(m×n))，其中α是反阿克曼函数，增长极慢，近似常数
• 空间复杂度：O(m×n)，存储并查集数据结构
• 优点：支持动态更新，适合岛屿数量可能变化的场景
• 缺点：实现相对复杂，常数因子较大

3.4 DFS迭代（栈实现）

核心思想：

使用栈模拟递归DFS，避免递归调用栈溢出的风险，同时保持DFS的深度优先特性。

算法思路：

Java代码实现：

import java.util.Stack;

class Solution4 {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int m = grid.length;
int n = grid[0].length;
int count = 0;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
dfsIterative(grid, i, j);
}
}
}

return count;
}

private void dfsIterative(char[][] grid, int i, int j) {
int m = grid.length;
int n = grid[0].length;

Stack<int[]> stack = new Stack<>();
stack.push(new int[]{i, j});

// 方向数组
int[][] directions = {{–1, 0}, {1, 0}, {0, –1}, {0, 1}};

while (!stack.isEmpty()) {
int[] current = stack.pop();
int row = current[0];
int col = current[1];

// 标记为已访问
if (grid[row][col] == '1') {
grid[row][col] = '0';

// 将相邻的陆地单元格压入栈中
for (int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];

if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n
&& grid[newRow][newCol] == '1') {
stack.push(new int[]{newRow, newCol});
}
}
}
}
}
}

性能分析：

• 时间复杂度：O(m×n)，每个单元格最多被访问一次
• 空间复杂度：O(m×n)，最坏情况下栈的大小可能达到网格大小
• 优点：避免递归栈溢出，保持DFS的深度优先特性
• 缺点：需要显式管理栈

3.5 BFS变体（使用方向数组优化）

核心思想：

在标准BFS基础上进行优化，使用方向数组简化代码，同时添加一些性能优化，如提前检查边界条件。

算法思路：

Java代码实现：

import java.util.LinkedList;
import java.util.Queue;

class Solution5 {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int m = grid.length;
int n = grid[0].length;
int count = 0;

// 方向数组
int[][] directions = {{–1, 0}, {1, 0}, {0, –1}, {0, 1}};

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;

// BFS
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
grid[i][j] = '0'; // 标记为已访问

while (!queue.isEmpty()) {
int[] current = queue.poll();
int row = current[0];
int col = current[1];

for (int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];

if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n
&& grid[newRow][newCol] == '1') {
queue.offer(new int[]{newRow, newCol});
grid[newRow][newCol] = '0'; // 标记为已访问
}
}
}
}
}
}

return count;
}
}

性能分析：

• 时间复杂度：O(m×n)，每个单元格最多被访问一次
• 空间复杂度：O(min(m, n))，队列的最大长度
• 优点：代码简洁，性能良好，适合大多数场景
• 缺点：与标准BFS相比无本质区别

4. 性能对比

4.1 复杂度对比表

4.2 实际性能测试

测试不同规模网格（m×n为网格大小）：

4.3 各场景适用性分析

5. 扩展与变体

5.1 岛屿的最大面积

题目描述：给定一个包含'1'和'0'的二维网格，找到网格中最大的岛屿面积（岛屿面积即岛屿中单元格的数量）。如果没有岛屿，则返回0。

class MaxAreaOfIsland {
public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int m = grid.length;
int n = grid[0].length;
int maxArea = 0;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
maxArea = Math.max(maxArea, dfs(grid, i, j));
}
}
}

return maxArea;
}

private int dfs(int[][] grid, int i, int j) {
int m = grid.length;
int n = grid[0].length;

if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != 1) {
return 0;
}

grid[i][j] = 0; // 标记为已访问

return 1 + dfs(grid, i – 1, j)
+ dfs(grid, i + 1, j)
+ dfs(grid, i, j – 1)
+ dfs(grid, i, j + 1);
}
}

5.2 统计封闭岛屿数量

题目描述：封闭岛屿是指完全由水包围的岛屿（即岛屿的边界上的每个单元格都与网格边界接触的单元格不是陆地）。

class NumberOfClosedIslands {
public int closedIsland(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int m = grid.length;
int n = grid[0].length;
int count = 0;

// 先淹没与边界相连的陆地（这些不是封闭岛屿）
for (int i = 0; i < m; i++) {
dfs(grid, i, 0); // 左边界
dfs(grid, i, n – 1); // 右边界
}

for (int j = 0; j < n; j++) {
dfs(grid, 0, j); // 上边界
dfs(grid, m – 1, j); // 下边界
}

// 统计剩余的岛屿（都是封闭岛屿）
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
count++;
dfs(grid, i, j);
}
}
}

return count;
}

private void dfs(int[][] grid, int i, int j) {
int m = grid.length;
int n = grid[0].length;

if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != 0) {
return;
}

grid[i][j] = 1; // 标记为已访问

dfs(grid, i – 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j – 1);
dfs(grid, i, j + 1);
}
}

5.3 岛屿的周长

题目描述：给定一个包含'1'和'0'的二维网格，其中'1'表示陆地，'0'表示水。网格中的单元格水平和垂直方向相连（对角线方向不相连）。网格完全被水包围，并且恰好有一个岛屿（即一个或多个相连的陆地单元格）。岛屿中没有"湖泊"（水域不与岛屿周围的水相连）。单元格是边长为1的正方形。网格是矩形，宽度和高度不超过100。计算岛屿的周长。

class IslandPerimeter {
public int islandPerimeter(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int m = grid.length;
int n = grid[0].length;
int perimeter = 0;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
// 每个陆地单元格贡献4条边
perimeter += 4;

// 如果上边有相邻陆地，减少两条边（当前单元格的上边和相邻单元格的下边）
if (i > 0 && grid[i – 1][j] == 1) {
perimeter -= 2;
}

// 如果左边有相邻陆地，减少两条边（当前单元格的左边和相邻单元格的右边）
if (j > 0 && grid[i][j – 1] == 1) {
perimeter -= 2;
}
}
}
}

return perimeter;
}
}

5.4 统计子岛屿数量

题目描述：给你两个m×n的二进制矩阵grid1和grid2，它们只包含'1'（陆地）和'0'（水）。如果grid2中的一个岛屿被grid1的一个岛屿完全包含，那么我们称grid2中的这个岛屿为子岛屿。请返回grid2中子岛屿的数量。

class CountSubIslands {
public int countSubIslands(int[][] grid1, int[][] grid2) {
if (grid2 == null || grid2.length == 0) {
return 0;
}

int m = grid2.length;
int n = grid2[0].length;
int count = 0;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid2[i][j] == 1) {
// 检查当前岛屿是否是子岛屿
if (dfs(grid1, grid2, i, j)) {
count++;
}
}
}
}

return count;
}

private boolean dfs(int[][] grid1, int[][] grid2, int i, int j) {
int m = grid2.length;
int n = grid2[0].length;

if (i < 0 || i >= m || j < 0 || j >= n || grid2[i][j] == 0) {
return true;
}

// 如果grid2是陆地但grid1是水，则不是子岛屿
if (grid1[i][j] == 0) {
return false;
}

grid2[i][j] = 0; // 标记为已访问

// 需要所有相邻部分都满足条件
boolean up = dfs(grid1, grid2, i – 1, j);
boolean down = dfs(grid1, grid2, i + 1, j);
boolean left = dfs(grid1, grid2, i, j – 1);
boolean right = dfs(grid1, grid2, i, j + 1);

return up && down && left && right;
}
}

6. 总结

6.1 核心思想总结

岛屿数量问题的核心是连通分量计数，关键在于：

6.2 算法选择指南

6.3 实际应用场景

6.4 面试建议

6.5 常见面试问题Q&A

Q：为什么只需要检查上下左右四个方向，而不检查对角线方向？ A：根据问题定义，岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成，对角线方向不算相邻。

Q：如果网格非常大（例如1000×1000），应该选择哪种算法？ A：对于非常大的网格，BFS通常更安全，因为它使用队列而不是递归栈，避免了栈溢出的风险。

Q：是否可以使用并查集解决这个问题？有什么优缺点？ A：可以。优点：支持动态更新，如果网格会随时间变化（陆地变水或水变陆地），并查集可以高效处理。缺点：实现相对复杂，常数因子较大。

Q：如何修改算法来统计每个岛屿的面积？ A：在DFS/BFS遍历时，可以计数访问的单元格数量。对于DFS递归，返回计数值；对于BFS，在队列遍历时计数。

Q：如果要求不能修改原网格，应该如何解决？ A：可以使用一个与网格同样大小的布尔数组来记录访问状态，但这会增加O(m×n)的空间复杂度。

Q：如何处理网格中有多个岛屿，且需要找到最大岛屿的情况？ A：在遍历过程中，对每个岛屿计算其面积，并记录最大值。可以使用DFS或BFS在标记岛屿的同时计数。

Q：如果网格是动态变化的（陆地和水会互相转换），如何高效地维护岛屿数量？ A：使用并查集数据结构，当单元格状态变化时，只需要更新与该单元格相关的连接关系，而不需要重新遍历整个网格。