跳到主要内容

岛屿数量

问题​

给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请计算网格中岛屿的数量。岛屿总是被水包围，每座岛屿只能由水平方向和/或垂直方向上相邻的陆地连接形成。

示例：

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

来源：LeetCode 200. 岛屿数量

答案​

方法一：DFS 深度优先（推荐）​

核心思路：遍历网格，遇到 '1' 就启动一次 DFS 把整个岛屿"淹掉"（标记为 '0'），岛屿计数 +1。

numIslandsDFS.ts
function numIslands(grid: string[][]): number {
  if (grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r: number, c: number): void {
    // 越界或不是陆地，返回
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') {
      return;
    }

    // 标记为已访问（淹没）
    grid[r][c] = '0';

    // 向四个方向扩展
    dfs(r + 1, c); // 下
    dfs(r - 1, c); // 上
    dfs(r, c + 1); // 右
    dfs(r, c - 1); // 左
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c); // 淹没整个岛屿
      }
    }
  }

  return count;
}

图解过程：

初始：
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

遇到 (0,0)='1'：count=1, DFS 淹没
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 1 1

遇到 (2,2)='1'：count=2, DFS 淹没
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1

遇到 (3,3)='1'：count=3, DFS 淹没
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

结果：3 个岛屿
复杂度分析
  • 时间复杂度：O(m×n)O(m \times n) — 每个格子最多访问一次
  • 空间复杂度：O(m×n)O(m \times n) — 最坏情况递归栈深度（全是陆地）

方法二：BFS 广度优先​

numIslandsBFS.ts
function numIslands(grid: string[][]): number {
  if (grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  function bfs(r: number, c: number): void {
    const queue: [number, number][] = [[r, c]];
    grid[r][c] = '0';

    while (queue.length > 0) {
      const [cr, cc] = queue.shift()!;

      for (const [dr, dc] of directions) {
        const nr = cr + dr;
        const nc = cc + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
          grid[nr][nc] = '0';
          queue.push([nr, nc]);
        }
      }
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        bfs(r, c);
      }
    }
  }

  return count;
}

方法三：并查集​

numIslandsUnionFind.ts
class UnionFind {
  parent: number[];
  rank: number[];
  count: number;

  constructor(grid: string[][]) {
    const rows = grid.length;
    const cols = grid[0].length;
    this.parent = new Array(rows * cols);
    this.rank = new Array(rows * cols).fill(0);
    this.count = 0;

    for (let r = 0; r < rows; r++) {
      for (let c = 0; c < cols; c++) {
        if (grid[r][c] === '1') {
          const id = r * cols + c;
          this.parent[id] = id;
          this.count++;
        }
      }
    }
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // 路径压缩
    }
    return this.parent[x];
  }

  union(x: number, y: number): void {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return;

    // 按秩合并
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    this.count--;
  }
}

function numIslands(grid: string[][]): number {
  if (grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  const uf = new UnionFind(grid);
  const directions = [[1, 0], [0, 1]]; // 只需要向下和向右

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        for (const [dr, dc] of directions) {
          const nr = r + dr;
          const nc = c + dc;
          if (nr < rows && nc < cols && grid[nr][nc] === '1') {
            uf.union(r * cols + c, nr * cols + nc);
          }
        }
      }
    }
  }

  return uf.count;
}
并查集适用场景

当需要动态合并和查询连通性时（比如在线添加岛屿），并查集比 DFS/BFS 更合适。对于静态查询，DFS 更简单。

常见面试追问​

Q1: 如何计算岛屿的最大面积？(LeetCode 695)​

答案：DFS 时返回面积：

function maxAreaOfIsland(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  let maxArea = 0;

  function dfs(r: number, c: number): number {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === 0) return 0;
    grid[r][c] = 0;
    return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) {
        maxArea = Math.max(maxArea, dfs(r, c));
      }
    }
  }

  return maxArea;
}

Q2: 如果不能修改原数组怎么办？​

答案：使用 visited 数组：

function numIslands(grid: string[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  let count = 0;

  function dfs(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (visited[r][c] || grid[r][c] === '0') return;
    visited[r][c] = true;
    dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (!visited[r][c] && grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Q3: 如何计算岛屿的周长？(LeetCode 463)​

答案：每个陆地格子贡献 4 条边，每两个相邻陆地减少 2 条边：

function islandPerimeter(grid: number[][]): number {
  let perimeter = 0;
  const rows = grid.length, cols = grid[0].length;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) {
        perimeter += 4;
        if (r > 0 && grid[r-1][c] === 1) perimeter -= 2;
        if (c > 0 && grid[r][c-1] === 1) perimeter -= 2;
      }
    }
  }

  return perimeter;
}

相关链接​