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

【LeetCode 热题 100】200. 岛屿数量——DFS

news 2025/7/21 7:02:26

Problem: 200. 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(M * N)
- 空间复杂度：O(M * N) (最坏情况)

整体思路

这段代码旨在解决一个经典的二维网格问题：岛屿数量 (Number of Islands)。问题要求计算一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格中，岛屿的总数。岛屿被定义为水平或垂直方向上相邻的 ‘1’ 连接而成的区域。

该算法采用了一种非常直观且高效的 深度优先搜索 (DFS) 策略，其核心思想是“沉岛”或“淹没”法。

遍历网格寻找新岛屿：
- 算法使用两层嵌套的 for 循环来逐一扫描网格中的每一个单元格 (i, j)。
- 当扫描到一个值为 '1' 的单元格时，这标志着我们发现了一个新岛屿（或者是一个已知岛屿的未被访问部分）。
发现新岛屿后的处理：
- 一旦发现一个 '1'，就将岛屿计数器 ans 加一。
- 紧接着，以这个发现的 '1' 单元格 (i, j) 为起点，立即调用一个 dfs 辅助函数。
DFS 沉岛/淹没过程：
- dfs 函数的任务是：从给定的起点 (i, j) 开始，通过递归的方式，找到所有与它相连的（水平或垂直）‘1’ 单元格，并将它们全部标记为已访问。
- 标记方法：代码中通过将 '1' 修改为 '2' 来实现标记。这是一种原地修改的技巧，避免了使用额外的 visited 数组。任何非 '1' 的值（如 ‘0’ 或 ‘2’）都表示水域或已访问过的陆地。
- 递归探索：在标记完当前单元格后，dfs 函数会向其上下左右四个方向进行递归调用，继续探索和淹没相邻的陆地。
- 边界与终止条件：dfs 的递归有明确的终止条件：
  - 越出网格边界（i 或 j 超出范围）。
  - 遇到水域或已访问过的陆地（grid[i][j] != '1'）。
  - 当满足这些条件时，递归会停止，并返回上一层。
算法的正确性保证：
- 由于每次发现 '1' 后，整个与之相连的岛屿都会被 dfs 一次性地“淹没”（标记为 ‘2’），因此，主循环在后续的扫描中不会再次将这个岛屿的任何部分计为新岛屿。
- 这就保证了每个岛屿只会被计数一次，从而得到正确的总数。

完整代码

class Solution {/*** 主函数：计算二维网格中岛屿的数量。* @param grid 一个由 '1' (陆地) 和 '0' (水) 组成的二维字符数组。* @return 岛屿的总数。*/public int numIslands(char[][] grid) {// ans: 用于累计岛屿的数量。int ans = 0;// 遍历网格的每一行for (int i = 0; i < grid.length; i++) {// 遍历网格的每一列for (int j = 0; j < grid[0].length; j++) {// 如果发现一个单元格是 '1' (未被访问过的陆地)if (grid[i][j] == '1') {// 这意味着我们发现了一个新的岛屿，计数器加 1。ans++;// 以此为起点，进行深度优先搜索，将整个岛屿“淹没”。dfs(grid, i, j);}}}// 返回最终的岛屿总数。return ans;}/*** 辅助函数：通过深度优先搜索（DFS）淹没与 (i, j) 相连的整个岛屿。* @param grid 网格* @param i 当前单元格的行索引* @param j 当前单元格的列索引*/private void dfs(char[][] grid, int i, int j) {// 递归的终止条件（边界检查）：// 1. 行索引越界 (i < 0 或 i >= grid.length)// 2. 列索引越界 (j < 0 或 j >= grid[0].length)// 3. 当前单元格不是未访问的陆地 (grid[i][j] != '1')if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {return;}// “沉岛”操作：将当前陆地单元格标记为已访问。// 这里用 '2' 作为标记，也可以用 '0'。grid[i][j] = '2';// 向四个方向递归探索，继续淹没相邻的陆地。dfs(grid, i + 1, j); // 向下dfs(grid, i - 1, j); // 向上dfs(grid, i, j + 1); // 向右dfs(grid, i, j - 1); // 向左}
}

时空复杂度

时间复杂度：O(M * N)

主循环：外层的两层 for 循环会遍历网格中的每一个单元格，总共 M * N 次，其中 M 是行数，N 是列数。
DFS 访问：dfs 函数虽然是递归的，但由于“沉岛”操作（将 ‘1’ 变为 ‘2’），每一个陆地单元格（‘1’）只会被 dfs 成功访问并处理一次。
综合分析：
- 整个算法的过程可以看作是对网格中的每个单元格进行了一次访问。
- 如果单元格是 ‘0’，主循环访问它，耗时 O(1)。
- 如果单元格是 ‘1’，主循环访问它，然后 dfs 会接管，访问并标记所有相连的 ‘1’。
- 最终，每个单元格都被访问了常数次。因此，总的时间复杂度与网格的大小成正比，即 O(M * N)。

空间复杂度：O(M * N) (最坏情况)

主要存储开销：该算法的空间开销主要来自于 DFS 的递归调用栈。
递归深度：调用栈的最大深度取决于 dfs 能够连续深入探索多远。
最坏情况：
- 考虑一个最坏的情况，即整个网格是一个巨大的、蜿蜒的岛屿，例如蛇形填满整个网格。
- 在这种情况下，dfs 的递归调用可能会深入到访问完所有 M * N 个单元格后才开始返回。
- 此时，递归栈的深度会达到 M * N。
- 因此，最坏情况下的空间复杂度为 O(M * N)。