题干与适用场景
给定一个 m × n 二维网格，元素只可能是字符 "1"（陆地）或 "0"（水）。两个陆地格只有在水平或垂直相邻时才连通；一座岛屿是一个最大的连通陆地集合。返回岛屿数量。
约束为 1 <= m, n <= 300。实现仍会防御空数组，避免把调用方约束写成运行时崩溃。默认允许修改输入网格；若调用方要求保留输入，就改用同尺寸的 visited 矩阵。
这是一道通用算法题，适合软件工程岗位的编码轮。它考察把矩阵转成隐式图、遍历连通分量，以及让代码与复杂度分析保持一致。
面试官考察点
强回答会先把每个陆地格视为顶点，把四方向相邻视为边。随后得到关键结论：扫描时每遇到一个尚未访问的陆地格，就发现了一个新的连通分量；从该格出发遍历并标记整座岛屿，之后不会重复计数。
实现细节同样重要。邻居应在入栈时标记，而非出栈时才标记，否则同一格可能被多个邻居重复压栈。迭代 DFS 避免一整块陆地导致递归调用栈过深。强回答还会准确说明：原地标记省掉了 visited 矩阵，但显式栈最坏仍需 O(mn) 空间。
普通回答往往只说“用 DFS”，却没有定义连通规则、修改输入的副作用、正确性不变量或对抗测试。
回答前需要澄清的问题
- 连通是否包含对角线？ 本题只算四方向；若包含八方向，只需扩充方向数组，答案可能改变。
- 能否修改输入？ 可以时把访问过的
"1"改成"0"；不可以时使用visited，时间不变但增加 O(mn) 存储。 - 网格是否规则且非空？ 题目保证矩形且非空；生产函数仍可对空输入返回 0。若允许锯齿数组，边界判断必须按当前行长度处理。
- 只求静态总数，还是持续加入陆地后查询？ 静态网格适合 DFS 或 BFS；动态加点更适合并查集。
- 数据规模与语言栈限制是什么？ 300×300 全为陆地时可能形成 90,000 层递归路径，因此这里选择显式栈。
30 秒回答框架
“我把陆地格看成隐式图的顶点，四方向相邻就是边。按行扫描网格；每次遇到 1，它一定属于尚未处理的新连通分量，所以岛屿数加一。然后用显式栈做 DFS，把可达陆地在入栈时改成 0。这样每个格最多入栈一次，不会重复计数，也规避了深递归。时间是 O(mn)，显式栈最坏 O(mn)。若输入不可修改，我会用 visited 矩阵保存访问状态。”
分步骤深入解答
第一步：从暴力重复搜索找到瓶颈
如果从每个陆地格都独立搜索其连通区域，同一座岛会被反复遍历。瓶颈不在找邻居，而在没有跨搜索保存“已经属于某个已计数分量”的状态。
全局扫描配合永久访问标记可消除重复：只有扫描遇到尚未标记的陆地时才启动一次搜索。
第二步：建立计数不变量
扫描到位置 (r, c) 时，之前启动过的每次 DFS 恰好标记了一整个岛屿。若当前格仍为 "1"，它不可能属于这些岛，因此必须是一个新岛的起点，计数加一。
从该点出发的 DFS 只沿四方向陆地移动，所以不会越过水连接两座岛；同时会访问所有可达陆地，因此这座岛以后不会再次触发计数。这同时证明了“不漏计”和“不重计”。
第三步：在入栈时标记
假设一个未标记格同时邻接两个已在栈中的格。若等到出栈才标记，这两个格都可能把它压栈。结果通常仍正确，但栈里出现重复工作，复杂度推导也变得松散。
发现邻居时立刻把它改为 "0"，再入栈。此后任何方向再次看到它都不会重复加入，保证每个陆地格最多入栈一次。
第四步：实现迭代 DFS
function numIslands(grid) {
if (grid.length === 0 || grid[0].length === 0) return 0;
const rows = grid.length;
const cols = grid[0].length;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let islands = 0;
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (grid[row][col] !== "1") continue;
islands += 1;
grid[row][col] = "0";
const stack = [[row, col]];
while (stack.length > 0) {
const [currentRow, currentCol] = stack.pop();
for (const [rowOffset, colOffset] of directions) {
const nextRow = currentRow + rowOffset;
const nextCol = currentCol + colOffset;
if (
nextRow >= 0 && nextRow < rows &&
nextCol >= 0 && nextCol < cols &&
grid[nextRow][nextCol] === "1"
) {
grid[nextRow][nextCol] = "0";
stack.push([nextRow, nextCol]);
}
}
}
}
}
return islands;
}扫描检查 mn 个格；每个陆地格最多入栈一次，并检查四个邻居，所以时间为 O(mn)。显式栈在全陆地网格上最坏保存 O(mn) 个坐标。输入被原地修改；若复制网格，复制本身也需要 O(mn) 时间和空间。
第五步：用边界和对抗用例验证
至少检查：空数组返回 0；单个水格返回 0；单个陆地格返回 1；全水返回 0；全陆地返回 1；只有对角线相邻的两个陆地返回 2；题目示例中的三个分离区域返回 3；300×300 全陆地不会触发递归溢出。
再检查输入副作用。若测试后还要复用原网格，应在调用前复制，或改用 visited。这项选择必须出现在接口说明中，不能藏在实现里。
第六步：比较替代方案
BFS 与迭代 DFS 的时间和最坏空间相同。需要按距离分层处理时选 BFS；这里只需要穷尽连通分量，两者都合适。递归 DFS 更短，只有在网格足够小或语言明确支持所需深度时才更简单。并查集适合陆地持续加入、每步都要返回岛屿数的版本；对一次静态计数会增加索引和集合维护成本。
高质量示范回答
“这道题等价于统计隐式无向图的连通分量。每个 1 是顶点，上下左右的 1 之间有边。我会扫描整个网格：如果当前位置还是 1，此前的搜索就没有到达它，因此发现了一座新岛，计数加一；随后从它开始迭代 DFS，把整座岛改成 0。
我会在邻居入栈时就标记，防止它被多个相邻格重复压栈。选择显式栈是因为 300×300 全陆地可能形成很深的递归路径。每格最多被处理一次，每次只看四个方向，所以时间 O(mn)，栈最坏 O(mn)。这个版本会修改输入；如果接口要求保留网格，我会把标记放进 O(mn) 的 visited 矩阵。最后我会用对角线不连通、全水、全陆地和空输入测试边界。”
这段回答把建模、计数依据、实现风险、副作用和验证连成一条推导链，不依赖背诵模板。
常见错误
- 把对角线也算作连通 → 改变题意并可能少算岛屿 → 方向数组只保留上下左右。
- 出栈时才标记 → 同一格可能被多个邻居重复压栈 → 发现有效邻居时立即标记再入栈。
- 宣称原地方案空间 O(1) → 忽略显式栈的最坏规模 → 报告辅助空间最坏 O(mn)。
- 递归 DFS 不讨论深度 → 大块连续陆地可能耗尽语言调用栈 → 使用迭代遍历或明确规模保证。
- 偷偷修改调用方数据 → 后续逻辑读到被清空的网格 → 在接口中说明副作用，必要时使用
visited。 - 每个陆地都重新搜索 → 同一分量被反复遍历 → 只从未访问陆地启动搜索。
- 只测常规矩形 → 漏掉空、全水、全陆地和对角线反例 → 用最小、极端和对抗用例覆盖假设。
追问及应对
追问一：如果不允许修改输入呢？
创建 m × n 布尔矩阵，在入栈时把对应位置设为已访问。计数不变量和时间 O(mn) 不变；额外存储明确增加到 O(mn)。若允许复制输入，复制与 visited 的渐进空间相同，只是语义不同。
追问二：如果对角线也算连通呢？
把方向从四个扩展为八个，遍历框架不变。应先用 [[1, 0], [0, 1]] 这类只对角相邻的例子确认预期，因为四方向答案为 2，八方向答案为 1。
追问三：如果陆地会逐个加入，并要求每次返回数量呢？
静态 DFS 会重复扫描。改用并查集：新陆地先让计数加一，再与每个已存在的相邻陆地合并；每次成功合并两个不同集合，计数减一。还要处理重复添加，避免重复加一。
追问四：如果网格非常稀疏且坐标范围巨大呢？
不应分配完整矩阵。用哈希集合保存实际陆地坐标，只遍历这些坐标并查四邻居；复杂度以陆地数 k 表示，期望时间 O(k)，访问集合和栈为 O(k)。这改变了输入表示，只有稀疏坐标列表可用时才成立。