岛屿数量

更新: 7/4/2026 字数: 0 字时长: 0 分钟

题目描述

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

岛屿由若干水平或垂直方向相邻的陆地连接而成。
你可以假设网格的四条边都被海水包围。

例如下面这个网格，答案是 3 座岛屿：
1 1 0 0 1
1 1 0 0 0
0 0 1 0 1
0 0 0 1 1
左上角一片 1 是一座岛，中间一个 1 是一座岛，右下角一片相连的 1 又是一座岛。

岛屿数量示意图：蓝色海水与相连的陆地方块组成若干座小岛，各岛用虚线圈出并编号

思路拆解

先想暴力解法

最直接的想法是靠「颜色/编号」区分连通块：给每块陆地涂上一个岛屿编号，扫描时如果相邻格子已有编号就沿用，否则开新编号——再借助并查集把相邻陆地不断合并，最后数一数有多少个不同的根。这套思路可行，但要维护并查集结构，代码相对繁琐。

点击展开暴力解法（并查集思路）

function numIslandsUF(grid) {
  if (!grid.length) return 0
  const rows = grid.length, cols = grid[0].length
  const parent = new Array(rows * cols)
  let count = 0
  // 初始化：每块陆地自成一个集合
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === '1') { parent[r * cols + c] = r * cols + c; count++ }

  const find = (x) => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x] } return x }
  const union = (a, b) => { const ra = find(a), rb = find(b); if (ra !== rb) { parent[ra] = rb; count-- } }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1') continue
      // 只需与右、下相邻陆地合并即可覆盖所有相邻关系
      if (r + 1 < rows && grid[r + 1][c] === '1') union(r * cols + c, (r + 1) * cols + c)
      if (c + 1 < cols && grid[r][c + 1] === '1') union(r * cols + c, r * cols + c + 1)
    }
  }
  return count
}

并查集能解，但需要额外维护父指针数组与路径压缩，理解与实现成本偏高。

推导最优解法：DFS 淹没法

换个更朴素的角度：只要遇到一块没被处理过的陆地，就一定是一座新岛屿的开始。于是把它整片相连的陆地一次性「淹没」掉（标记为已访问或直接改成 '0'），这样这座岛以后就不会被重复统计了。

于是算法变得极简：

从左上到右下逐格扫描网格；
遇到陆地 '1' 且未被淹没，就令岛屿数 +1；
从这块陆地出发做 DFS（或 BFS），把上下左右四连通的所有陆地全部淹没；
继续扫描，直到遍历完所有格子。

核心思路

每座岛只会在它「第一块被扫描到的陆地」处贡献一次计数，随后被 DFS 彻底淹没。因此扫描一遍网格、每次发现新陆地就 +1，就能得到岛屿总数。四个方向的扩散是连通性的关键。

DFS 淹没一座岛的过程如下图：从任意一块陆地出发，沿四个方向不断吞并相连的陆地，直到整座岛都被染色：

DFS 淹没岛屿示意：从一块陆地出发向上下左右扩散，把整座岛逐格标记为已访问，岛屿数加一

动画演示

下面用样例网格完整演示 DFS 淹没法。主循环扫描指针（紫色高亮）逐格前进，发现新陆地时岛屿数 +1，随后 DFS 沿四个方向把整片相连陆地淹没（按岛屿编号着色），右侧同步展示递归栈：

DFS 淹没法 · 岛屿数量演示

样例网格：4 × 5（1 = 陆地，0 = 海水）

当前阶段：准备已发现岛屿：0

DFS 递归栈（栈顶在上）

空

海水 0未访问陆地 1扫描指针DFS 当前格已淹没（按岛着色）

从左上角开始逐格扫描网格。遇到还没访问过的陆地(1)，就说明发现了一座新岛屿，岛屿数 +1，再把整片相连陆地淹没。

步骤 0 / 59

完整代码

function numIslands(grid) {
  if (!grid || grid.length === 0) return 0
  const rows = grid.length
  const cols = grid[0].length
  let count = 0

  // 从 (r, c) 出发淹没整片相连陆地
  const dfs = (r, c) => {
    // 越界或遇到海水/已淹没，直接返回
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') 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
}

BFS 写法

如果担心 DFS 递归过深导致栈溢出，可把 dfs 换成用队列的 BFS：发现新陆地时入队，循环取出队首并把四邻居的陆地入队、同时淹没，逻辑与 DFS 等价，复杂度相同。

复杂度分析

设网格有行列：

解法	时间复杂度	空间复杂度	说明
DFS 淹没法			每格最多访问一次；最坏递归深度为格子总数
BFS 淹没法			队列最多存储一层的宽度
并查集			为反阿克曼函数，近似常数

每个格子只会被扫描主循环访问一次、被 DFS 访问一次，因此时间与格子总数成正比。

边界与易错点

空网格：grid 为空或行数为 0 时应直接返回 0，否则 grid[0] 会报错。
元素是字符不是数字：LeetCode 本题的 '1'/'0' 是字符串，比较时要用 grid[r][c] === '1'，写成 === 1 会永远不成立。
只算四连通：仅上下左右相邻算相连，斜对角不算同一座岛。若把四方向写成八方向，答案会偏小。
越界判断要放在最前：DFS 递归入口先判断 r/c 是否越界，再访问 grid[r][c]，否则会数组越界。
淹没不能漏：进入 DFS 后必须立刻把当前格标记为 '0'（或 visited），否则会无限递归、重复计数。
不想修改原网格：若要求保留输入，可另开一个 visited 布尔数组代替直接改 grid，逻辑一致。
递归深度：网格极大（如全是陆地）时 DFS 递归可能很深，工程中可改用显式栈或 BFS 规避栈溢出。

岛屿数量 ​

题目描述 ​

思路拆解 ​

先想暴力解法 ​

推导最优解法：DFS 淹没法 ​

动画演示 ​

完整代码 ​

复杂度分析 ​

边界与易错点 ​