hot100 岛屿数量(200)

本题采用深度优先搜索DFS网格染色剪枝算法又称“沉岛标记法”或“网格洪泛填充法”解决二维矩阵连通域计数问题。其核心本质是将全局稀疏陆地节点的检索转化为从任意未访问陆地出发的四向递归图遍历利用原地状态修改直接消除重复访问并实现物理剪枝。当前提供的源码实现了在时间复杂度 O(m * n) 和额外空间复杂度 O(m * n) 条件下的连通域全盘扫描最终走向是精准输出二维网格中独立拓扑连通岛屿的绝对总量。一、 问题本质与数据模型对于大小为 m x n 的二维网格矩阵 grid题目给出了两个核心的拓扑结构约束四向连通性定义只有在水平方向左右或竖直方向上下相邻的陆地字符 1 才能被判定为物理互通对角线方向不算连通。边界水域包围网格的四周物理边缘外隐式设定为完全被水字符 0 包围。如果在网格的双重遍历扫描中仅仅对遇到的每个 1 触发简单的计数器累加将会导致同一个连续的陆地岛屿被重复计数例如一个 2 x 2 的全陆地矩阵会被错误计为 4 个岛屿。为了破除这种数据重复呈现导致的计数失真算法引入了“种子触发现场染色模型”。当外层的线性双重循环首次碰撞到未被处理的陆地 1 时认定捕获到了一个新岛屿的火种。算法在将全局计数器ans递增后立即拉起内层 DFS 染色函数。该函数以当前坐标为圆心向上下左右四个维度呈树状分叉式深探。在每一个步进到的有效陆地单元格上直接原地将其字符改写为 2标记为已访问/沉岛。这种原地物理篡改破坏了原数据的分布使得后续的外层循环无法再次感知到该陆地节点从而实现了彻底的边界隔离。二、 算法演进对比在解决网格连通分量岛屿计数问题时不同图论算法在时空开销及架构设计上存在以下差异解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷并查集法 (Union-Find)O(m * n * alpha(m * n))O(m * n)将每个坐标视作独立节点扫描并合并相邻陆地最终统计根节点数动态合并开销较高需要额外的父节点数组及秩数组物理内存空间广度优先搜索 (BFS)O(m * n)O(min(m, n))利用显式队列按层向四周扩散染色队列大小受限于连通域的最长边界需要维护外部辅助队列结构若网格规模极大可能造成堆内存剧烈起伏深度优先搜索当前解法O(m * n)O(m * n)双重循环检索火种触发四向深探通过原地修改物理状态实现无锁剪枝依赖运行时调用栈在整张网格全为陆地的极端拓扑下栈深可达 O(m * n)三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于外层双重循环核验与内层 DFS 的四向边界防护网其内部决策分支证明如下1. 种子触发分支if (grid[i][j] 1)执行ans并激活dfs(grid, i, j)。物理意义在线性物理扫描中锁定了一块全新的、完全与已知岛屿孤立的未知陆地。触发岛屿总数的质变累加并以该点为根节点发动清扫。2. 原地状态覆写grid[i][j] 2;执行将当前陆地标志修改为状态码 2。数学证明通过修改内存中的字符消除了额外申请布尔型visited[m][n]矩阵的内存开销。字符 2 在后续的分支判定中等同于水域 0 的逻辑防护效应确保该节点彻底退出历史搜索舞台。3. 方向向量集中控制int[][] dir ...执行利用常数大小的步进偏移矩阵通过for (int[] d : dir)驱动状态演进。数学证明将繁琐的四段式手工硬编码分别编写上下左右四组 if 语句收拢至一处循环模型中降低了分支预测的逻辑开销。4. 边界安全核验拦截if (x 0 x grid.length ...)执行验证新坐标是否越过网格的物理边界并核验grid[x][y] 1是否成立。数学证明双重防护机制。前四项边界判定彻底杜绝了数组下标越界异常ArrayIndexOutOfBoundsException末尾的条件则实现了精准制导只有真正的、未染色的原生陆地才能获得压栈递归的权限其余状态直接在当前层级被丢弃。四、 算法执行状态机步进示例以输入局部矩阵grid [ [1, 0], [1, 1] ]为例规模 2 x 2 全局计数器ans及内层递归调用栈的状态机演进过程如下表所示步骤当前扫描/访问坐标 (i, j)单元格状态数值状态判定与执行分支核心物理剪枝与染色动作全局计数器 ans 与栈状态初始(0, 0)1满足外层扫描命中触发新岛屿ans 递增为 1拉起内层 DFS(0, 0) 探测ans 1, 栈: [ (0,0) ]1(0, 0) [内]1执行原地染色并测试四向偏移量将 grid[0][0] 强制置为 2向下发现 (1, 0) 为 1ans 1, 栈: [ (0,0), (1,0) ]2(1, 0) [内]1执行原地染色并测试四向偏移量将 grid[1][0] 强制置为 2向右发现 (1, 1) 为 1ans 1, 栈: [ (0,0), (1,0), (1,1) ]3(1, 1) [内]1执行原地染色发现四周无有效 1将 grid[1][1] 强制置为 2四向核验失败触发回溯ans 1, 栈: 逐渐出栈至空4(0, 1)0外层继续直线扫描不满足触发条件越过水域单元格不触发任何内层逻辑ans 1, 栈空5其余已被染色的坐标2外层继续直线扫描因不等于 1 遭拦截已被物理标记为 2完美规避二次计数流程结束ans 1, 扫描完结五、 源码实现class Solution { public int numIslands(char[][] grid) { // 全局岛屿独立连通域计数器 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) { // 计数器执行自增 ans; // 激活深度优先搜索染色机清除当前连通体内的所有陆地状态 dfs(grid, i, j); } } } // 返回最终统计出的不连通岛屿绝对总量 return ans; } // 静态方向矩阵映射依次代表向右、向下、向左、向上四个物理移动偏移行程 private int[][] dir new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; private void dfs(char[][] grid, int i, int j) { // 核心原位剪枝将当前坐标强制覆写为 2将其从潜在搜索集合中物理剔除 grid[i][j] 2; // 迭代处理四个方向的步进演进 for (int[] d : dir) { int x i d[0]; int y j d[1]; // 四向安全边界防护网确保索引不越出矩阵实体且目标格点必须为待处理陆地 1 if (x 0 x grid.length y 0 y grid[0].length grid[x][y] 1) { // 满足准入条件向下一层级压栈递归执行染色 dfs(grid, x, y); } } } }六、 复杂度分析1. 时间复杂度O(m * n)分析算法的外层执行了完整的双重嵌套循环其基准扫描步数等于网格单元格总数 m * n。对于内层的 DFS 而言尽管包含了递归调用但由于每个陆地单元格在被首次触碰时便立即执行了状态变迁由 1 覆写为 2因此任何一个网格格点进入递归体的次数至多为 1 次。在各节点内部四向偏移核验属于常数阶操作 O(1)。结论整个网格搜索路径的原子比较与赋值次数与矩阵总规模呈严格的线性正比关系时间复杂度收敛于 O(m * n)。2. 空间复杂度O(m * n)分析算法直接利用了输入矩阵进行原地状态标记没有申请任何与输入规模成正比的外部物理存储矩阵空间开销 O(1)。然而其空间的动态波动完全受限于递归函数的运行时调用栈。在最坏情况下整张网格全部为陆地且图拓扑退化为蜿蜒盘旋的单向蛇形链条递归调用的栈深度将达到最大极限值即 m * n。结论在最坏网络拓扑下最大额外系统栈空间复杂度表现为 O(m * n)在完全不连通的极稀疏矩阵下空间复杂度收敛于常数阶 O(1)。