企业官网建设流程全解析

Leetcode 73，矩阵置零，这题我在不同阶段刷了至少三遍，每次都有新理解。它在 Leetcode 热门 100 题里位置靠前，题目描述只有一句话：给定一个 m x n 的矩阵，如果某个元素为 0，则将其所在行和列的所有元素都设为 0，并且要求原地修改。很多人第一眼觉得这是道简单题，可真要在面试里把常数空间解法讲清楚，卡壳的往往是两个地方：为什么第一行第一列能当标记，以及处理顺序为什么不能乱。这篇文章就把这题彻底拆开，从 O(mn) 空间、O(m+n) 空间一路讲到 O(1) 空间的矩阵内标记法，每一版本都会解释设计动机，顺便把实际刷题时见过的错误提交都整理出来。

1. 先看懂题目：矩阵置零到底在考什么

1.1 题目原意到底是什么意思

题目输入是一个 m 行 n 列的整数矩阵。要求是：遍历这个矩阵，只要发现某个位置 (i, j) 上的值是 0，就把第 i 行整行和第 j 列整列全部变成 0。注意这个规则是“连锁式”的：多个 0 互相影响，但只需要考虑原始矩阵里的 0，不需要考虑因为置零新产生的 0。

举个例子：

输入： [[1, 1, 1], [1, 0, 1], [1, 1, 1]] 输出： [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

矩阵正中间有一个 0，所以中间行、中间列全部被置零，四个角保持不变。

再来看一个多 0 的例子：

输入： [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] 输出： [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

左上角和右上角都是 0，所以第一行、第一列、第四列都被置零。中间那些元素因为不在任何带 0 的行或列上，所以保留原值。

题目还有一个硬性要求：原地修改。也就是说不能用额外矩阵去存结果，必须在传入的这个二维数组上直接改。Leetcode 上现在的数据范围里 m、n 一般到 200 以内，元素是 int 类型。正因为尺寸不大，时间复杂度和空间复杂度的优化就变成了这道题唯一的考察重点。

1.2 为什么是高频题

Leetcode 热门 100 题里收录它，面试题库里也常见它，原因很实际。第一，读题没有门槛，不需要任何算法背景，几分钟就能让候选人进入状态。第二，它背后藏着一组漂亮的复杂度梯度：复制矩阵是 O(mn) 空间，标记数组是 O(m+n) 空间，矩阵内标记是 O(1) 空间。面试官可以用同一道题，通过“还能不能更省？”这句话，一层层测出你优化方案的思路能力。

第三，也是最重要的一点，它考察的是“原地修改时的信息覆盖问题”。数据要存在原数组里，又要用原数组传递状态，这本来就是工程里很常见的矛盾。很多系统设计、缓存策略、内存复用场景都会遇到类似问题。而矩阵置零恰好把这个矛盾压缩到最小规模，让候选人用一小段代码展示自己处理这种问题的意识。会做这题的人不少，但能在几分钟内把原理讲清楚、把顺序问题避开的候选人，确实不算多。

2. 从最笨的解法到 O(m+n) 空间

2.1 复制矩阵：能跑但不是最优

最容易想到的方案是复制一份原矩阵，然后遍历副本，发现某个位置是 0，就去原矩阵里把它所在的行和列全部置零。

def set_zeroes_copy(matrix): m, n = len(matrix), len(matrix[0]) copy = [row[:] for row in matrix] for i in range(m): for j in range(n): if copy[i][j] == 0: for r in range(m): matrix[r][j] = 0 for c in range(n): matrix[i][c] = 0

这版代码思路直白，人不会写错，但它有两个问题。空间上，复制一份完整矩阵要 O(mn) 的额外内存；时间上，虽然主循环是 O(mn)，但每次遇到 0 都要扫一行和一列，最坏情况下（矩阵全是 0）会退化到 O(mn * (m+n))。

这个版本的价值只在于作对比。如果你在面试里写它，面试官大概率会追问“能不能不复制”，然后顺势引到更优解法。所以它适合作为一个思考起点，但不适合作为最终提交。

2.2 行、列标记数组：O(m+n) 空间的中间解

复制矩阵缺点明显，于是自然会想到：我们不复制整张矩阵，只记录“哪些行需要清零、哪些列需要清零”。这就是两个标记数组的思路。

def set_zeroes_linear(matrix): m, n = len(matrix), len(matrix[0]) row_zero = [False] * m col_zero = [False] * n for i in range(m): for j in range(n): if matrix[i][j] == 0: row_zero[i] = True col_zero[j] = True for i in range(m): for j in range(n): if row_zero[i] or col_zero[j]: matrix[i][j] = 0

这个解法是两遍扫描：第一遍做标记，第二遍根据标记修改矩阵。空间复杂度降到了 O(m+n)，时间复杂度稳定在 O(mn)，已经是一个很理想的答案了。

为什么第一遍必须先标记、第二遍再修改？因为如果在第一遍里发现 0 就立刻把整行整列置零，那么新产生的 0 会干扰后续的判断，比如一个本来不该清零的行会因为另一个行被清零后产生出的 0 而被误判。标记数组本质上是把“哪些位置需要处理”这个信息先完整地记录下来，避免修改过程中的副作用互相干扰。这个“先记录、后执行”的思想，也是接下来常数空间解法的灵魂。

2.3 三种方案的空间复杂度对比

把三种思路放在一张表里看，梯度非常清楚：

注意，时间复杂度下限就是 O(mn)，因为你至少要把每个元素看一遍才知道它是不是 0。所以后两种方案在时间上已经做不出区别，比拼的就是谁能在空间上再抠出一个量级。而常数空间的解法，依赖的是同一个矩阵里“第一行”和“第一列”这两块区域来存储标记信息。

3. 常数空间的矩阵内标记法

3.1 把第一行第一列当成“公告栏”

既然需要 O(m+n) 的标记信息，而矩阵里本身就有 m 行和 n 列，一个自然的想法是：用矩阵自己的第一行来标记每一列是否需要清零，用第一列来标记每一行是否需要清零。也就是说，把第一行和第一列当作一个“公告栏”。

具体规则是这样的：扫描矩阵内部（从第二行第二列开始），如果发现 matrix[i][j] == 0，就在公告栏上写两个信息——matrix[i][0] = 0 表示第 i 行需要清零，matrix[0][j] = 0 表示第 j 列需要清零。

为什么这个方案不会出错？因为公告栏上的每个 0 都对应一个真实存在的 0 所在的行或列。比如 matrix[i][0] 被写成 0，是因为第 i 行内部确实有一个 0，那么第 i 行整行清零本来就是正确操作；matrix[0][j] 被写成 0，是因为第 j 列内部确实有一个 0，那么第 j 列整列清零也没有问题。所以标记过程并不会制造“错误信号”。

但公告栏有个特别坑的地方：matrix[0][0] 这个位置同时属于第一行和第一列。它到底是“第一行有 0”的标记，还是“第一列有 0”的标记？单看这个位置无法区分。所以必须额外用两个布尔变量，先把第一行和第一列原始状态备份下来。这一步就是所有错误提交的万恶之源。

3.2 完整可提交的 O(1) 空间代码

先给一版可以直接提交的 Python 实现，每一行注释都对应一个关键步骤：

class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: m, n = len(matrix), len(matrix[0]) # 备份第一行、第一列原始是否有 0 row0_has_zero = any(matrix[0][j] == 0 for j in range(n)) col0_has_zero = any(matrix[i][0] == 0 for i in range(m)) # 用第一行、第一列做公告栏 # 注意从 (1,1) 开始扫，避开公告栏自身 for i in range(1, m): for j in range(1, n): if matrix[i][j] == 0: matrix[i][0] = 0 matrix[0][j] = 0 # 根据公告栏修改内部区域 # 同样从 (1,1) 开始，先把中间处理好 for i in range(1, m): for j in range(1, n): if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0 # 最后处理第一行和第一列 if row0_has_zero: for j in range(n): matrix[0][j] = 0 if col0_has_zero: for i in range(m): matrix[i][0] = 0

C++ 版本同样给出，面试时用 C++ 写也是常见要求：

class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); bool row0 = false, col0 = false; for (int j = 0; j < n; ++j) { if (matrix[0][j] == 0) { row0 = true; break; } } for (int i = 0; i < m; ++i) { if (matrix[i][0] == 0) { col0 = true; break; } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (row0) { for (int j = 0; j < n; ++j) matrix[0][j] = 0; } if (col0) { for (int i = 0; i < m; ++i) matrix[i][0] = 0; } } };

代码不算长，但四个阶段的顺序一个都不能错：备份、标记、处理内部、还原边缘。

3.3 为什么必须额外记录 row0 和 col0

很多人看代码时会疑惑：第一行第一列不是已经被当成公告栏了吗，为什么还要两个 bool 变量？直接看反例最直观。

考虑一个矩阵：

[[0, 2, 3], [4, 5, 6], [7, 8, 9]]

唯一的 0 在 matrix[0][0]，那么第 0 行和第 0 列都应该被置零。预期结果是：

[[0, 0, 0], [0, 5, 6], [0, 8, 9]]

如果不备份 row0 和 col0，只靠公告栏，那么矩阵里唯一的 0 就落在公告栏本身，它不会再去触发任何内部元素的标记。于是标记阶段结束，公告栏上干干净净，第二遍处理内部时什么都不做，最终结果变成：

[[0, 2, 3], [0, 5, 6], [0, 8, 9]]

matrix[0][1] 和 matrix[0][2] 没有被清零，第一行明显错了。这正是因为 matrix[0][0] 的“自身是数据”含义和“自己是公告栏”含义叠在一起时，必须单独把它拆出来记一遍。

反过来说，如果第一行本身有 0 但不在第一列，比如：

[[1, 0, 3], [4, 5, 6]]

第 0 行有 0，所以整行要清零。但标记阶段只会记录 matrix[0][1] 对应第 1 列需要清零，第一行自身是否清零这件事没有任何标记会触发。如果不备份 row0，最终第一行会保留成 [1, 0, 3] 而不是 [0, 0, 0]，同样是错的。所以这两个变量一个都不能省。

3.4 处理顺序决定成败

这个解法里，顺序不是习惯问题，而是正确性问题。

第一阶段必须先备份第一行第一列的状态，因为后面的标记阶段会往这两个位置写入 0，等到最后想恢复时原始状态已经丢了。

第二阶段只能从 (1,1) 开始扫描，不能从 (0,0) 开始。因为公告栏上的 marker 本身也是矩阵元素，如果把第一行和第一列当成普通数据参与扫描，公告栏上的 0 会被当成“真实存在的 0”，导致原本不需要清零的行列被误判。举例来说，矩阵如果是：

[[1, 2, 3], [4, 0, 6], [7, 8, 9]]

预期结果是：

[[1, 0, 3], [0, 0, 0], [7, 0, 9]]

标记阶段正确执行后，matrix[1][0] 和 matrix[0][2] 会被写成 0。如果第三阶段从 (0,0) 开始重新扫描，看到 matrix[0][2] == 0 会以为第一行有真实的 0，于是把第一行整行清零，最终得到错误的 [[0,0,0],[0,0,0],[7,0,9]]。这就是公告栏信号和数据混淆的典型事故。

第三阶段处理内部区域，也必须先从 (1,1) 开始，并且第三阶段不能修改第一行第一列。原因超级简单：内部的每个格子要判定自己是否需要置零，依据就是公告栏上的标记，如果你在第三阶段提前把公告栏清了，后面的格子就没有参照物了。

最后阶段才能还原第一行第一列。此时内部已经全部处理完，公告栏变成废纸一张，怎么改都不影响结果。

4. 实操中一定会踩的坑

4.1 反例一：没备份第一行/第一列的状态

把 3.3 里的反例浓缩成一句话：如果矩阵的第 (0,0) 位置是 0，不备份就一定会丢状态。我在实际提交记录里看到过不少版本，把 row0 和 col0 的检查放在标记阶段之后，结果就是整个矩阵正确率靠运气。

还有一个衍生错误是：备份时只备份一行或一列，忘了另一个。比如只检查了第一行，没检查第一列，结果第一列原本有 0 时，整个第一列不会被清零。一行代码的缺失，会导致测试用例里凡是第一列有 0 的样例全部挂掉。

提示：备份阶段一定用两个独立变量，一个管行、一个管列，不要图省事合并成一个。

4.2 反例二：从 (0,0) 开始扫描标记

这个坑我见过不止一次。代码写出来逻辑很像“扫描所有元素，遇到 0 就在公告栏标记”，于是循环范围写成 from 0 to m-1、from 0 to n-1。看起来覆盖面更广，实际上一旦第一行或第一列本身有 0，公告栏就会混入真实数据信号，后续处理会产生连锁误判。

正确的做法是 (1,1) 到 (m-1,n-1)，把第一行第一列隔离在外。它们的信息已经通过 row0 和 col0 单独保存了，不需要再进入主扫描。

4.3 反例三：边界尺寸和全 0 矩阵

边界条件也是错误高发区。m 或 n 等于 1 时，矩阵退化成一维。比如：

[[0, 1]]

预期是把这一个 0 所在的行和列都置零，得到 [[0,0]]。用标准解法走一遍：row0 为 true，col0 为 true，内部区域为空，最后 row0 和 col0 处理完成后，结果是 [[0,0]]，正确。

再比如：

[[1, 1], [1, 0]]

只有一个 0 在右下角，预期结果应该是：

[[1, 0], [0, 0]]

用代码跑一次也能通过。这类单行单列矩阵最怕的其实是数组下标越界，比如在 n==0 时访问 matrix[0][0]。好在 Leetcode 现在限制 m、n 至少为 1，但如果面试官把矩阵尺寸改成可能为 0，就需要在前面加一个空矩阵判断。

全 0 矩阵是好消息也是陷阱。说好是因为任何正确代码都能输出全 0；说陷阱是因为如果你在本地用全 0 用例调代码，几乎所有错误版本都能“恰好通过”，根本测不出问题。所以自测时必须补一个“只有一个 0 在角落”的用例，那才是考验备份逻辑的场景。

4.4 纸上模拟一次完整流程

用一个中等矩阵手工走一遍，顺序感会更清晰。假设输入是：

[1, 2, 3] [4, 0, 6] [7, 8, 9]

第一步检查第一行，没有 0，所以 row0=False；检查第一列，没有 0，col0=False。

第二步从 (1,1) 开始扫描：(1,1) 的 4 不是 0，(1,2) 的 0 出现，于是标记 matrix[1][0]=0、matrix[0][2]=0。公告栏状态变为：

[1, 2, 0] [0, 0, 6] [7, 8, 9]

第三步根据公告栏修改内部：(1,1) 的判定条件是 matrix[1][0]==0，成立，所以置 0；(1,2) 同理置 0；(2,1) 的判定条件是 matrix[2][0]==0 或 matrix[0][1]==0，两者都是假，所以保留 8；(2,2) 的 matrix[0][2]==0，成立，所以置 0。得到：

[1, 2, 0] [0, 0, 0] [7, 8, 0]

第四步 row0 和 col0 都是 False，第一行第一列不动。最终结果是：

[1, 0, 3] [0, 0, 0] [7, 0, 9]

与预期完全一致。注意第二步矩阵中间那个 0 的位置原本是 6，但在第三步被正确清零了。公告栏传递信息的过程，在这个模拟里看得非常清楚。

5. 延伸思考：和它同类的算法题

5.1 “只遍历一次”真的可能吗

很多人看完 O(1) 解法会问：能不能只遍历一遍就搞定？答案是做不到。原因是矩阵置零的问题本质是一个“全局决策”问题：第 (i,j) 个位置最终是否为 0，取决于整个矩阵里是否存在某个 0 与它同行或同列。当你第一次扫到 (i,j) 时，矩阵后半部分还没看，你不可能知道它后面会不会蹦出一个 0 来决定它的命运。

所以任何单遍扫描算法都需要在扫描过程中把“信息”存到某个地方，而存信息的地方要么是额外数组，要么是已经扫过的原矩阵区域。我们上面的 O(1) 方案实际上就是这种思路：一边扫一边把信息写进公告栏，第二遍再根据公告栏做最终修改。所以最优复杂度是两遍扫描，这不是偷懒，而是信息论层面的下限。

5.2 矩阵操作类的同源题目

矩阵置零的“用矩阵自身存状态”思路，和几道经典题是互通的。

第一道是 Leetcode 48 旋转图像。原地旋转矩阵时，四个元素一组进行轮换，面临的也是“被覆盖后信息丢失”的问题，所以必须用临时变量暂存一个值。这和置零题里备份 row0 的逻辑如出一辙。

第二道是 Leetcode 289 生命游戏。整个棋盘需要同时更新，更新规则依赖每个格子的旧状态。如果你直接从左上角开始改，后面格子拿到的是新状态，结果就全错了。经典解法是引入中间状态值，比如用 2 表示“原来是 0、新状态是 1”，用 3 表示“原来是 1、新状态是 0”，最后再统一转化。这本质上也是在原数组里编码“旧状态+新状态”的双重信息。

第三道是原地哈希系列，比如 Leetcode 41 缺失的第一个正数、Leetcode 442 数组中重复的数据。这些题用数组下标当哈希桶，用符号替代布尔标记，核心逻辑同样是“在原数据内部做标记”。如果你能真正吃透矩阵置零，再刷这几道题会有一种打通经脉的感觉。

5.3 常见追问题汇总

面试官拿到这道题后，常见的追问大概有几种。第一种是“空间还能再省吗”，直接把话题引向 O(1) 解法。第二种是“第一行第一列本身有 0 怎么办”，考察你对信息覆盖的理解。第三种是“能否只遍历一次”，就是 5.1 里的问题。第四种是“如何保证不误伤没有 0 的行列”，考察对公告栏标记语义的理解。

还有一些偏开放的追问，比如“如果矩阵非常大，一行放不下内存怎么办”。这种场景通常考虑按块读取，或者用稀疏方式存储 0 的位置，但已经超出 Leetcode 考察范围了。能说出“稀疏场景下记录 0 的位置列表可能比 O(1) 扫描更省”这种话，会显得你有工程感觉。

6. 刷题和面试的实战建议

6.1 周赛限时环境下怎么写不丢分

矩阵置零在周赛里属于签名题，很多人一分钟就能写完，但每次周赛的提交错误率并不低。问题基本都出在“想当然”三个字上。限时环境下最稳的做法是背住一个固定套路，按顺序写四块代码：备份、标记、内部处理、边缘还原。写完后再用脑子跑两组用例，一组是角落有 0，一组是第一行有 0 但第一列没有。

我在 Leetcode 周赛里观察到，错误代码的典型特征是：只写了标记和还原，省略了备份；或者把扫描起点写成了 0。遇到这种题，别追求炫技，直接写最稳的 O(1) 模板就好。时间上花不到三分钟，剩下的时间留给后面的题。

6.2 面试作答的最优策略

面试时不要一上来就写最优解，那样反而显得像背答案。更好的节奏是：先口述复制矩阵的朴素思路，承认它空间不够好；然后给出 O(m+n) 的标记数组方案，并说明为什么需要两遍扫描；最后再抛出“能不能用第一行第一列当标记”的想法，现场推导出 O(1) 解法。

这个递进过程本身就是面试官想看的思维路径。每一层都基于上一层的不足做优化，显得有逻辑而不是背模板。如果直接在白板上写 O(1) 解法，面试官大概率会追问代码里的每个细节，这时候你能把 row0、col0 的备份原理讲透，反而更容易拿到高分。

我自己的经验是，在写代码前先用一句话跟面试官对齐思路：“我把第一行当列标记，把第一列当行标记，然后单独处理第一行第一列自身的 0。”这句话一说，面试官就知道你不是在默写代码。

6.3 建议的自测用例清单

刷题和真实面试里，自测用例越全越稳。下面这份清单基本能覆盖所有边界：

这些用例不用全跑，但写完后至少挑角落、单行、首行有 0 这三个重点验证，就能把绝大多数 bug 挡在提交前。

最后再分享一个我自己的小习惯：每次写完这题后，我会在注释里把四个阶段标上“备份”“标记”“内部处理”“边缘还原”四个词。这看起来很多余，但确实帮我在面试紧张状态下保持清醒，不至于手一滑就把顺序写乱。Leetcode 73 是个小题目，但它的优化路径和结构意识，能迁移到非常多后续题目里，值得花时间认真写几遍。