企业官网建设流程全解析

矩阵置零（Set Matrix Zeroes）应该是 LeetCode 73 题，也是我在面试中特别爱考的一道题。原因很简单：它从暴力解到 O(m+n) 空间再到 O(1) 空间的递进非常自然，每一层都能看出候选人是在背题还是真的理解了"原地算法"的本质。这题表面上只是"把含 0 的行列都清零"，但真正动手写的时候你会发现一堆细节：标记放哪里、什么时候清零、首行首列本身含 0 怎么办、单行单列矩阵会不会越界。这些坑踩一遍印象会非常深，所以我想把这题的完整思路、代码实现和常见翻车点一次讲清楚，适合正在刷题准备面试的人，也适合想把"状态压缩"思想用熟练的开发者。

1. 题干拆解与三条递进路线

1.1 题目到底在问什么

原题描述很简洁：给定一个m x n的矩阵，如果某个元素是0，就把该元素所在的行和列全部置为0。进阶要求是尽量使用更少的额外空间，最好做到常数空间。

这里有几个隐藏信息容易被忽略。第一，"所在行和列"意味着一个零会连锁触发整行整列清零，但这些被清零的位置不应该继续作为"触发器"去清零别的行列。也就是说，如果你在处理过程中把所有新变 0 的格子当作"发现了一个 0"，就会发生雪崩效应，最终整个矩阵全变成 0。第二，题目明确要求原地修改，不允许直接返回一个新的矩阵。第三，进阶的 O(1) 空间并不是让你烧掉所有额外空间，它指的是除输入矩阵本身以外，只使用固定数量的额外变量。

换句话说，这题考的不只是你会不会写双重循环，而是你能不能想清楚"信息记录在哪里"以及"执行顺序如何设计"。

1.2 三种解法：从直观到极致

我第一次做这题时的第一反应是复制一份矩阵，然后扫描原矩阵，凡是遇到 0，就去副本里把对应行列全部设 0，最后把副本搬回原矩阵。这种解法思路最直白，时间上如果优化得好可以达到 O(mn) 级别的扫描次数加 O(mn) 级别的置零操作，但空间是 O(mn)。面试时主动提出这个方案不是不行，但要立刻意识到它不是最优，而且会暴露你对"原地"要求理解不够。

稍微进阶一点的思路是记录信息而不是直接动手改。既然我们真正关心的是"哪些行需要清零"和"哪些列需要清零"，那么可以用两个数组，比如rowMark和colMark，长度分别是 m 和 n。先完整扫描矩阵，一旦发现matrix[i][j] == 0，就标记rowMark[i] = true、colMark[j] = true。扫描结束后，再根据这两个标记统一把对应行和对应列置零。这样空间是 O(m+n)，并且避免了前面说的"边扫边改导致连锁污染"问题。

再从 O(m+n) 到 O(1) 的关键一步是意识到：rowMark本质上就是 m 个布尔值，colMark本质上就是 n 个布尔值，这些信息不需要专门申请数组，完全可以借矩阵的第一行和第一列来存放。第一行有 n 个格子，正好对应 n 列；第一列有 m 个格子，正好对应 m 行。用矩阵自身的"首行首列"来存储标记，配合两个额外布尔变量兜底，就可以把额外空间压缩到常数级。这就是标准的三分法：先扫描并记录，再根据记录清内部区域，最后处理首行首列本身。

2. 核心原理：为什么"首行首列"能当标记

2.1 矩阵里天然的"坐标轴"

如果你已经理解了 O(m+n) 的标记数组方案，那么 O(1) 方案的核心思想就是"把标记数组塞进矩阵自己身上"。矩阵的第一行有 n 个位置，我完全可以用matrix[0][j]是否为 0 来表示第 j 列是否需要清零；矩阵的第一列有 m 个位置，我完全可以用matrix[i][0]是否为 0 来表示第 i 行是否需要清零。

这个设计为什么自然？因为矩阵存在天然的"坐标轴"：第一行本身就是所有列的索引位，第一列本身就是所有行的索引位。把行标记和列标记分别放在第一列和第一行，读取时也只需要访问固定位置，逻辑非常干净。

但这里立刻出现一个矛盾：第一行和第一列既要承担"标记位"的功能，它们自己也是矩阵的一部分，本身也可能需要被清零。比如第一行原本就有一个 0，那么第一行最终必然要整行清零；但是如果我在扫描过程中直接把第一行的某些位置改成 0 作为标记，会不会把"原本第一行有 0"这个原始信息覆盖掉？

这个矛盾正是这题最容易出错的地方，解决的办法是额外用两个布尔变量提前保存第一行、第一列原始状态下是否包含 0。我习惯命名为firstRowHasZero和firstColHasZero。它们在主干扫描前先记录好"原始状态"，之后第一行、第一列就可以放心变成标记容器，不用担心信息丢失。

2.2 为什么必须"先记录、后动手"

很多第一次写这题的人会本能地这么做：遍历到matrix[i][j] == 0，立刻把第 i 行和第 j 列全部置 0。这个写法看起来一分钟就能写完，但实际跑起来完全错。

问题在于执行顺序的污染。假设一个 3x3 矩阵中间位置matrix[1][1] == 0，你立刻把第 1 行改成 0，于是matrix[1][2]变成 0；继续遍历到matrix[1][2]这个格子时，你看到它是 0，又去把第 2 列清成 0。凡是"被清零"的格子都被当成了"原始 0"，这种连锁反应最终会把整个矩阵全部变成 0。就像你在清理房间时，把一桶水打翻在地板上，又踩着自己的脚印到处走，最后整个房间都是脚印。

正确的执行顺序必须是两阶段或三阶段。第一阶段只负责"侦察"，把所有需要清零的行列信息全部收集到标记位中；第二阶段才根据标记统一执行清零，而且清零的过程中不要再修改标记位本身。我通常把整个过程分成三趟扫描：第一趟扫描内部区域并更新首行首列标记；第二趟根据首行首列的标记，把内部"非首行非首列"的格子清零；第三趟单独处理第一行和第一列本身。这样每一趟的职责单一，逻辑就很好验证。

2.3 O(1) 空间真的够吗

从信息论的角度来想一件事：最终结果需要区分"每一行是否有 0"和"每一列是否有 0"，这本质上是 m+n 个独立的布尔信息。你不可能真的用少于 m+n 个比特来精确表达这些信息，但矩阵本身提供了m + n - 1个首行首列格子来存储这些信息，再加上两个额外的布尔变量兜底，恰好可以装下所有必要的标记。这就是"状态压缩"的经典应用：把原本独立的两个数组，压缩进矩阵已有的存储空间里。

额外两个布尔变量是常数，符合 O(1) 的空间要求。这里的 O(1) 指的是与输入规模无关的固定额外空间，不是"什么额外空间都不用"。面试时如果被问"你这不算零空间吧"，你可以明确回答：常数空间的意思是额外空间不随 m、n 增加而增长，两个变量永远是两个变量。

3. 手写实现：分三趟扫描的完整代码

3.1 第一步：先记录首行首列的原始状态

无论你怎么设计，首行首列在后续会被改写成标记，所以必须先保存它们的原始"含零状态"。这一步需要放在任何修改之前。

def setZeroes(matrix): m = len(matrix) n = len(matrix[0]) first_row_has_zero = False first_col_has_zero = False # 记录第一行原始是否包含 0 for j in range(n): if matrix[0][j] == 0: first_row_has_zero = True break # 记录第一列原始是否包含 0 for i in range(m): if matrix[i][0] == 0: first_col_has_zero = True break

这里要注意一个细节：如果矩阵只有一行（m == 1），上述两个 for 循环其实检查的是同一批元素，只是视角不同。不过这个步骤只是赋值布尔变量，并不会出错。真正的坑出现在后面的清零阶段，我放到第 4 节边界条件里专门讲。

3.2 第二步：用首行首列充当标记数组

从(1, 1)开始遍历内部区域，遇到 0 就同时更新两个标记位：matrix[0][j] = 0表示第 j 列需要清零，matrix[i][0] = 0表示第 i 行需要清零。这一步绝对不能从第 0 行第 0 列开始，因为那会把第一行第一列原本要保存的标记弄混。

# 使用首行首列记录需要清零的行列 for i in range(1, m): for j in range(1, n): if matrix[i][j] == 0: matrix[0][j] = 0 matrix[i][0] = 0

直觉上这像是在"破坏"首行首列的数据，其实不是破坏，而是有意的覆盖：到了这一步，我们已经不需要第一行第一列原有的具体数值了，因为first_row_has_zero和first_col_has_zero已经保存了它们是否含 0 的关键状态。第一行第一列剩余的价值就是作为标记位。

3.3 第三步：根据标记清零内部区域

现在内部区域可以安全处理了。遍历从(1, 1)到(m-1, n-1)，如果matrix[0][j] == 0或者matrix[i][0] == 0，就把matrix[i][j]置 0。

这一步的本质是：第 j 列要清，是因为标记行matrix[0][j]为 0；第 i 行要清，是因为标记列matrix[i][0]为 0。两者只要有一个成立，这个格子就得归零。

for i in range(1, m): for j in range(1, n): if matrix[0][j] == 0 or matrix[i][0] == 0: matrix[i][j] = 0

你会发现这个遍历方向是固定的：从前往后还是从后往前都不影响内部清零，因为内部清零的结果只会用到首行首列标记，不会反过来修改首行首列标记。所以内部区域的清零属于"纯消费者"，不具备"写标记"的能力，不会产生连锁污染。

3.4 第四步：单独处理首行首列

这一步放在最后很关键。如果先处理了首行首列，那内部区域还在用首行首列的标记，你把标记清零了内部就没法清。因此必须先清内部，再清首行首列。

if first_row_has_zero: for j in range(n): matrix[0][j] = 0 if first_col_has_zero: for i in range(m): matrix[i][0] = 0

注意首行和首列的交点是matrix[0][0]，如果第一行需要清，它会被置 0；如果第一列也需要清，它也会被置 0，结果都一样。这个交点不需要特别处理，两个 if 顺序谁先谁后无所谓。

把完整的代码拼起来就是上面这几段。我习惯用 Python 写演示代码，因为逻辑最直白。如果用 C++ 或其他语言，唯一要注意的是矩阵可能为空，需要提前判空。LeetCode 原题通常保证矩阵非空，但实际工程中建议加上if not matrix or not matrix[0]: return这样的防护。

3.5 手动推演两个样例

我建议刷题时一定要手推样例，这个习惯能帮你提前发现逻辑漏洞。拿一个最简单的 3x3 矩阵举例：

原始矩阵： 1 1 1 1 0 1 1 1 1

第一步，保存首行原始状态：第一行是[1, 1, 1]，没有 0，所以first_row_has_zero = False；第一列是[1, 1, 1]，没有 0，所以first_col_has_zero = False。

第二步，遍历内部区域时发现matrix[1][1] == 0，因此把matrix[0][1]置 0（表示第 1 列要清零），把matrix[1][0]置 0（表示第 1 行要清零）。此时矩阵变成：

1 0 1 0 0 1 1 1 1

注意matrix[1][0]原本是 1，现在被改成 0，这是有意的标记，不要误以为它是"原始 0"。

第三步，根据标记清内部区域。遍历(1,1)到(2,2)：matrix[1][1]因为matrix[0][1] == 0且matrix[1][0] == 0被置 0；matrix[1][2]因为matrix[1][0] == 0被置 0；matrix[2][1]因为matrix[0][1] == 0被置 0；matrix[2][2]两个标记都不是 0，所以保持不变。

1 0 1 0 0 0 1 0 1

第四步，因为first_row_has_zero为 False，第一行不动；因为first_col_has_zero为 False，第一列不动。最终结果正确：

1 0 1 0 0 0 1 0 1

再举一个包含首行首列零的场景，例如matrix = [[0, 1, 1], [1, 1, 1], [1, 1, 1]]。这里原始第一行含 0，所以first_row_has_zero = True，第一列不含 0，所以first_col_has_zero = False。第二步遍历内部时，没有发现内部 0，所以首行首列标记不变。内部清零阶段因为首行标记里的matrix[0][0]是 0，会导致matrix[1][0]和matrix[2][0]在内部清零阶段被置为 0？其实不会，因为内部清零遍历从(1,1)开始，判断条件matrix[0][j] == 0 or matrix[i][0] == 0。对于matrix[1][1]，matrix[0][1]是 1，matrix[1][0]是 1，都不为 0，所以不清零。但对于matrix[1][0]和matrix[2][0]，它们属于第一列区域，不在内部清零范围内，而是由最后处理第一列的first_col_has_zero决定。因为first_col_has_zero为 False，这一列不会被单独清。可原始矩阵的第一行有 0，意味着第一列最终应该被整体清零吗？对。因为matrix[0][0]是 0，而第 0 列的所有元素都应该被置 0。这一步由谁来完成？答案是内部清零阶段会把matrix[1][0]清为 0？回到代码，内部清零阶段遍历的是 i 从 1 到 m-1、j 从 1 到 n-1，也就是matrix[1][0]和matrix[2][0]根本不在遍历范围内，它们只能靠最后的first_col_has_zero来处理。但first_col_has_zero这里为 False，那matrix[1][0]和matrix[2][0]就不会被清了，正确结果应该是第一列全为 0，这里就错了。

等一下，需要重新审视这个样例。matrix = [[0,1,1],[1,1,1],[1,1,1]]，原始matrix[0][0] == 0，所以第一行含 0 且第一列含 0。我前面手动判断first_col_has_zero时说的是第一列是[0, 1, 1]，所以应该是 True 而不是 False。重新推演：first_row_has_zero = True，first_col_has_zero = True。这样最终第一行、第一列都会被清零，结果正确。这正好说明一个关键注意点：判断第一列是否含 0 时，必须把matrix[0][0]算进去，它属于第一列的第一个格子。千万不要漏了它。

第二个样例推演后会发现，即使内部区域没有 0，首行首列自身的 0 也会通过最后两步带动第一行第一列整体清零，所以原始首行首列有 0 的情况完全依赖那两个布尔变量，这也再次说明提前保存状态非常重要。

4. 边界条件与隐藏陷阱

4.1 单行矩阵和单列矩阵

如果矩阵只有一行，即 m == 1，那么第一行就是全部。核心逻辑会退化成：只要这行里有任何一个 0，整行都为 0。用我上面的四步流程也能跑对，因为first_row_has_zero会记录到 0，最终将第一行整体清零；内部区域由于i从 1 开始，循环体根本不会执行。但要注意，first_col_has_zero的保存逻辑里，matrix[i][0]访问的是matrix[0][0]，如果该元素本身是 0，first_col_has_zero也会变 True，最后处理第一列时只会把matrix[0][0]置 0，反正整行都是 0，看起来没区别。

如果担心极端情况，可以在开头先处理 m == 1 或 n == 1 的单独逻辑，这样代码更直白。比如：

if m == 1: has_zero = any(x == 0 for x in matrix[0]) if has_zero: matrix[0] = [0] * n return

这种冗余分支虽然代码多几行，但能避免后续很多边界讨论。实际面试中，我会先写通用解法，再补一句"如果只有一个行列，需要单独处理"，这比让面试官自己发现你漏了边界要好得多。

4.2 遍历方向的问题

很多题解在第三步内部清零时选择从下往上遍历，也就是i从m-1到1，j从n-1到1。这是因为他们用的是另一种标记策略：先处理第一行第一列本身，再从下往上清。在我这个版本里，内部清零是纯消费标记，所以从上往下、从下往上都一样。

但如果你在内部清零的同时把matrix[i][0]或matrix[0][j]当作清零对象去修改，就会出现方向依赖。例如提前把第一列整体清零，那么之后的内部元素判断matrix[i][0] == 0全部成立，整个内部都会被误清。所以有一个非常重要的原则：只要内部清零还没结束，就绝对不要动首行首列的标记值。

4.3 首行首列已经被标记污染了怎么办

这里我指的不是"用 0 作为标记会丢失信息"这个问题，而是当第一行第一列里本来就有 0 时，标记位和原始数据重叠。例如第一行第 3 列本来就是 0，它在扫描前就被记录到matrix[0][2] == 0，同时我们又用它作为"第 3 列是否需要清零"的标记。这时标记信息没有被破坏，因为它本身就是 0，表示第 3 列需要清零，这与原始数据恰好一致。

真正容易被忽略的是第一行第一列交叉点matrix[0][0]。如果它原始是 0，那么matrix[0][0] == 0同时表示"第 0 行需要清"以及"第 0 列需要清"，两个布尔变量都会被置 True。如果它原始不是 0，但内部某个位置matrix[i][0]或者matrix[0][j]在扫描时把matrix[0][0]二次标记，这也是可以的，因为matrix[0][0]作为标记本身没有特殊含义，真正的首行首列原始含零状态已经保存在两个布尔变量里了。所以matrix[0][0]最后是否为 0，完全由first_row_has_zero和first_col_has_zero共同决定，不需要额外恢复逻辑。

4.4 关于用特殊值替代标记的讨论

有人会问：能不能遍历时遇到 0 不用 0 做标记，而是用-1或者其他特殊值？比如把标记写成matrix[0][j] = -1，避免和原始 0 混淆。这在某些变体题里确实用得更多，比如 LeetCode 289 生命游戏里，用中间状态编码。但在本题里，用 0 做标记是完全充分的，因为首行首列在保存原始状态后，已经不再需要区分"原始 0"和"标记 0"。而且题目最终所有清零操作的结果都是把元素置为 0，标记值和最终值天然一致，不需要还原。反过来如果你用-1做标记，最后还得把所有-1改回 0，徒增一遍扫描，所以不推荐。

只在一个场景下需要特殊值：如果你不能预先记录首行首列的原始状态，必须在遍历过程中同步标记，那么用非 0 特殊值可以帮助区分。但既然我们已经用first_row_has_zero、first_col_has_zero保存了状态，这个需求就不存在了。

4.5 时间复杂度的严谨验证

很多人以为 O(1) 空间方案一定比 O(m+n) 空间方案慢，其实不会。我的实现一共做了四趟扫描：第一趟保存首行首列状态，扫描量是 O(n + m)；第二趟遍历内部，O(mn)；第三趟清内部，O(mn)；第四趟清首行首列，O(m + n)。总计 O(mn)，和 O(m+n) 空间版本完全一样。常数项稍微大一点，4 倍左右，但大 O 表示下没有区别。在实际运行中，矩阵规模稍大一点，时间差异完全可以忽略。

空间复杂度方面，除了两个布尔变量和几个循环计数器，没有任何随输入规模增长的额外存储。写代码时要注意别为了省事使用set、list收集坐标，那样就又变成 O(mn) 空间了。

5. 面试追问、变体和思维迁移

5.1 面试官喜欢追问的几个问题

第一个高频追问是"为什么不用 HashSet 存坐标？"你可以回答：HashSet 最坏情况下要存 mn 个坐标，空间 O(mn)；即使用两个 Set 分别存行和列，也是 O(m+n)，但我希望把额外空间压到常数，所以借用首行首列存储标记。接着面试官可能会追问"你这两个布尔变量算不算额外空间？"你要明确：算，但它们是常数，所以整体空间复杂度是 O(1)。

第二个追问是"能不能只用一次遍历完成？"严格来说不可能在一次遍历里同时完成"发现全部 0"和"清零行列"，因为你扫描到最后一个元素时可能才发现前面的行需要清零，不可能回头处理。但如果你不在乎标记被覆盖，可以选择"先记录到首行首列、第二趟再清"，这是两趟算法。所谓一次遍历的写法，其实还是把首行首列原始状态保存后做标记，本质上也是两阶段，只是把部分操作合并到同一次循环里，代码看起来更短，但可读性会下降。

第三个追问是"如果把矩阵换成链表或者图，这题还能用 O(1) 额外空间吗？"这类开放问题考察的是你是否理解标记的本质。链表可以用快慢指针、用节点本身的引用做标记；图可以用节点的颜色状态做标记，但都要看你能否在不额外分配存储的情况下保存信息。通常回答到"信息必须存在某个既有位置里"这个层面就够了。

5.2 相关题目与思维模型串联

矩阵置零是"原地哈希"这一类思维的代表。同类的还有寻找重复数、缺失数：利用数组下标本身当作哈希表的位置，把元素数值映射到索引，通过修改数组元素的正负号来标记状态。再比如 LeetCode 289 生命游戏，用位运算在一个 int 里同时保存旧状态和新状态，本质上也是状态压缩。还有旋转图像，虽然不涉及标记，但也在练习"原地操作矩阵"的感觉。

如果你能把这题的思维模型抽象出来，它其实是"无额外存储条件下如何保存 m+n 个布尔信息"。答案分两步：找一块已经存在但暂时可以被覆盖的区域当标记区；在覆盖前先把这块区域的原始关键信息迁移到少量兜底变量里。这个抽象可以迁移到很多类似场景，我在做字节跳动、某大厂面试的模拟题时发现，很多 hard 题考的是同一套路子的不同变形。

5.3 写在最后的一点私货

我见过很多候选人在 5 分钟内就写出了"看起来正确"的 O(m+n) 版本，但你要让他现场优化到 O(1)，很多人会卡住。卡住不是因为他们不知道可以借首行首列，而是因为一时想不到"先把第一行第一列本身的信息保存下来"这个细节。其实只要你记住：任何"借用现有空间做标记"的方案，都必须为被借用空间原本的关键信息准备逃生通道，这个坑就不会再踩。矩阵置零是一道很值得反复刷的题，每次重写都会提醒我：原地算法最怕的不是算法难，而是覆盖了不该覆盖的旧信息。动手写之前先花 10 秒在纸上把每一趟的读写区域圈出来，比盲目敲代码有效得多。