刚把 LeetCode 热题 100 刷到第 18 题矩阵置零。这道题在 Hot 100 里的位置挺靠前标签是数组、哈希表、矩阵但实际上手会发现它真正的考点只有一个原地修改的边界控制。如果你只是想把题过了十五分钟就能写完但如果你在面试里被问到这道题面试官大概率会追问能不能把空间复杂度降到 O(1)——这时候才是真正拉开差距的地方。这篇就把这道题从暴力到最优的完整思路、代码实现和踩坑细节都盘一遍当作自己的刷题笔记也希望对正在刷 Hot 100 的朋友有帮助。1. 题目拆解到底在考什么1.1 题目描述与真正的考点题目本身很简短给定一个 m x n 的矩阵如果某个元素是 0就把这个元素所在的行和列全部设为 0。听着像个模拟题但这里有一个非常关键的隐含约束——必须在原矩阵上直接修改也就是 in-place。这句话才是整道题的题眼。如果你能额外开一个一模一样大小的矩阵来记录哪些位置需要置零那这道题就是纯粹的遍历没有任何难度。但原地两个字直接把你用额外矩阵的路堵死了逼着你想办法在有限的信息存储空间内完成这件事。另外还要注意题目里对0的定义矩阵元素是整数可能是正数、负数当然也包括 0 本身。所以不能用特殊值替换这种投机取巧的办法——因为你不知道矩阵里原本有没有这个特殊值。1.2 为什么把标记信息存哪是核心矛盾我们换个角度看这道题一个矩阵里出现若干个 0我们需要知道的信息是——哪些行要清零、哪些列要清零。这个信息量其实很小最多也就是 m 个行标记和 n 个列标记。但问题是这些标记存在哪如果再开两个数组各存 m 和 n 个布尔值空间复杂度就是 O(mn)。这在绝大多数语言里都不是什么大负担但题目既然问了能不能做到 O(1)就一定存在一个更巧妙的方案。答案的关键在于矩阵的第一行和第一列本身就可以当作标记数组来用。你不需要额外开辟空间矩阵第二行第二列到最后一个元素只需要负责扫描而第一行第一列负责记录。这就是用矩阵自身存储元信息的思路——在算法题里算是一种很典型的空间复用技巧。2. 三条解法路线从最好想到最优2.1 暴力标记法O(mn) 空间能 AC 但是不及格先看最简单直观的方案复制一份原矩阵然后遍历原始矩阵遇到 0 就在副本矩阵上把对应行和列全部清零最后把副本赋回原矩阵。这个方案的代码非常好写逻辑零难度时间复杂度为 O(mn)空间复杂度为 O(mn)。能不能通过 LeetCode能。但这道题的目的绝对不是为了让你这样写面试官看到这种解法大概率会追问一句还能不能优化所以这种方案了解一下就行不建议作为最终答案。2.2 行列表格法O(mn) 空间面试最稳的答案暴力法的问题在于我们其实不需要完整复制整个矩阵只需要知道哪几行、哪几列需要清零。思路还是先扫描但这次只记录信息创建两个布尔数组row[m]和col[n]初始都为 false。遍历矩阵如果matrix[i][j] 0就把row[i] true、col[j] true。再次遍历矩阵如果row[i]或col[j]为 true就把matrix[i][j]置为 0。这个方案的时间复杂度同样是 O(mn)但空间复杂度降到了 O(mn)代码依然非常直观。如果你在面试中一时间想不出 O(1) 空间的方案先把这个答案写出来是完全 OK 的至少证明了你的思路是清晰的然后再尝试优化空间。2.3 常数空间标记法用矩阵自身记录信息接下来就是这道题最核心的进阶方案能不能把空间复杂度降到 O(1)既然不能用额外数组那就得在矩阵本身上做文章。仔细想想我们需要的标记信息是第 i 行是否需要清零和第 j 列是否需要清零这是两类信息分别存在哪里答案呼之欲出——用第一行存列标记用第一列存行标记。具体来说先遍历整个矩阵第一行和第一列除外如果某个位置matrix[i][j] 0就把matrix[i][0] 0标记第 i 行需要清零同时把matrix[0][j] 0标记第 j 列需要清零。再次遍历矩阵这次从第二行第二列开始只要当前位置所在行的第一列是 0或者所在列的第一行是 0就把这个位置置为 0。最后处理第一行和第一列本身——注意这里有个大坑我们马上会讲。这个方案的思路非常漂亮空间复杂度 O(1)时间复杂度依然是 O(mn)。但第一次写的时候非常容易踩坑因为第一行和第一列既被当成了标记数组又是矩阵本身的真实数据两者混在一起边界情况稍不留神就错了。3. 第一行第一列标记法的血泪细节3.1 为什么第一行第一列不能直接改这是最容易翻车的地方很多人第一次写常数空间方案时都会写出这样的代码# 错误示例 for i in range(m): for j in range(n): if matrix[i][j] 0: matrix[i][0] 0 matrix[0][j] 0然后第二步扫描的时候发现全矩阵都变成 0 了。为什么因为当你扫描到matrix[0][1]这个位置时如果它本身是 0你会把matrix[0][1]所在的第一行标记为 0。但问题是——第一行本身就参与了标记它既是被扫描的对象又是记录列标记的存储区。举个例子[1, 0, 3] [4, 5, 6] [7, 8, 9]如果按上面的错误写法先处理(0,1)这个 0我们会把matrix[0][1] 0本身已经是 0和matrix[0][1] 0标记列——这看起来没问题。但别忘了我们还在遍历第一行后面的matrix[0][2]也就是 3它的位置在第一行而第一行只要有一个 0这一整行最后都要清零。问题在于我们用矩阵的第一行和第一列来存储标记但第一行和第一列本身也可能包含 0这些 0 到底是标记信息还是真实数据如果不加以区分逻辑就乱了。3.2 双变量标记法用两个 bool 兜底正确做法是先做特判用两个额外的布尔变量记录第一行和第一列原本是否有 0。这也是这道题唯一需要增加的两个变量。完整思路分四步走用两个布尔变量first_row_has_zero和first_col_has_zero分别记录第一行和第一列是否原本就有 0。从(1,1)开始遍历整个矩阵跳过第一行和第一列遇到 0 就把它映射到第一行第一列上——即matrix[i][0] 0和matrix[0][j] 0。再从(1,1)开始遍历根据第一行第一列的标记把对应位置置 0。最后根据两个布尔变量处理第一行和第一列本身。这里最关键的就是第一步和第二步的分离。一定要在上面第 2 步的遍历中跳过第一行和第一列这样第一行第一列上的 0 就全部是标记信息不会和真实数据混淆。3.3 完整参考代码先贴一份 C 版本也是力扣上最常见的写法class Solution { public: void setZeroes(vectorvectorint matrix) { int m matrix.size(); int n matrix[0].size(); bool firstRowHasZero false; bool firstColHasZero false; // 检查第一行是否有 0 for (int j 0; j n; j) { if (matrix[0][j] 0) { firstRowHasZero true; break; } } // 检查第一列是否有 0 for (int i 0; i m; i) { if (matrix[i][0] 0) { firstColHasZero 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; } } } // 根据标记将对应位置置 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 (firstRowHasZero) { for (int j 0; j n; j) { matrix[0][j] 0; } } // 处理第一列 if (firstColHasZero) { for (int i 0; i m; i) { matrix[i][0] 0; } } } };Python 版本思路一模一样class Solution: def setZeroes(self, matrix: List[List[int]]) - None: m, n len(matrix), len(matrix[0]) first_row_has_zero any(matrix[0][j] 0 for j in range(n)) first_col_has_zero any(matrix[i][0] 0 for i in range(m)) 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 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 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这里要注意的是Python 解法中any()的使用很简洁但有些人可能觉得不明显改用普通 for 循环也行不影响正确性。4. 复杂度对比与面试追问4.1 三种方案的时间和空间对比把三种方案放在一起看差异一目了然方案时间复杂度空间复杂度适用场景暴力复制法O(mn)O(mn)不推荐仅作思路起点行列标记法O(mn)O(mn)面试保底答案代码最不易错常数空间法O(mn)O(1)最优解面试加分项有一个点值得强调这三种方案的时间复杂度完全相同。也就是说从 O(mn) 到 O(mn) 再到 O(1)优化的只是额外空间而空间优化的代价是代码复杂度显著上升、边界情况增多。这就给了一个很重要的面试策略——如果你在面试环境下没办法保证常数空间方案的代码一次写对写 O(mn) 版本反而更稳妥。面试官要的是能跑对的代码而不是一个炫技但是有 bug 的半成品。4.2 面试官可能追问的延伸问题这道题问完之后经常会有延伸追问第一个追问是能不能只用一个变量做到 O(1) 空间这个问题其实有变体网上有方案只用col0一个变量记录第一列是否有 0然后用matrix[0][0]本身记录第一行是否有 0。这个方案是可行的但代码上需要调整处理顺序少一个 bool 变量代价是对matrix[0][0]这个位置的语义要非常清楚。我个人的建议是如果面试官不主动问就用两个变量的版本更容易解释如果他追问能不能再少一个变量可以说出思路但不建议现场改写。第二个追问是如果矩阵特别大一次放不进内存怎么办这就涉及到外部排序和分块处理的思想了属于系统设计层面的问题已经超出这道题的范围。简单的回答方向是可以按块读取矩阵分别处理每一块中的 0 所在的行列信息但整体思路本质上还是 O(mn) 标记法。第三个追问是二维矩阵的行列标记还能用在哪些场景这个问题其实挺开放的。一般来说凡是涉及某个位置的值需要影响它所在的行和列的问题都可以考虑用这种哨兵行/哨兵列的思路。比如棋盘类问题、岛屿类问题的变体、甚至图像处理里的某些区域填充算法都可能用得到。4.3 为什么这个思路比哈希表更优雅其实拿到这道题你可能会先想到用哈希表存储有 0 的行号和列号。这个思路和 O(mn) 数组标记法本质一样只是用哈希表代替了数组。在矩阵尺寸很大的时候如果 0 的数量非常稀少哈希表确实能节省一定空间但最坏情况下 0 的数量接近 mn哈希表的空间复杂度就是 O(mn)和数组没有区别而且哈希表还有额外的常数开销。常数空间标记法最优雅的地方在于它把标记信息和原数据融合在同一块内存里完美利用了第一行和第一列反正最后大概率要清零这一特点。不过需要注意如果矩阵只有一行或者只有一列那么这个思路会退化成什么情况下面来单独分析这种极端情况。5. 边界情况与常见 bug 实录5.1 最容易翻车的三个位置写完代码一定要自己过一遍边界测试尤其是下面三个场景场景一矩阵只有一行。比如[[1, 0, 1]]。这时first_row_has_zero为 true中间扫描部分从 (1,1) 开始这个循环根本不会执行因为 m1。直接走到底部处理第一行得到[0, 0, 0]这是正确的。但这里要小心的是如果矩阵只有一列同理。场景二矩阵第一行和第一列本身没有 0但中间区域有 0。比如[1, 2, 3] [4, 0, 6] [7, 8, 9]两个 bool 变量都是 false中间扫描把第一行第二列和第三行第一列标记为 0第二步扫描把(1,2)和(2,1)置 0最终得到[1, 0, 3] [0, 0, 0] [0, 8, 9]注意(0,0)这个位置没有被改变因为第一行和第一列本身没有 0这个结果是正确的。场景三第一行和第一列交叉处也就是(0,0)位置本身就是 0。 比如[0, 1, 2] [3, 4, 5] [6, 7, 8]这个例子非常经典。按我们的逻辑first_row_has_zero和first_col_has_zero均为 true最终整个矩阵全部变成 0。这是符合题意的因为(0,0)为 0意味着第 0 行和第 0 列都要清零而这两者的交叉点也是 0所以整个矩阵全部清零。逻辑完全正确。5.2 调试技巧用最小样例验证边界我自己刷这道题的时候发现一个非常有效的验证方法写完之后不要立刻提交先手动跑四个最小规模的用例[[0]]单元素矩阵结果应该是[[0]]。[[0, 1]]一行两列结果应该是[[0, 0]]。[[1], [0]]两行一列结果应该是[[0], [0]]。[[1, 2], [3, 4]]没有任何 0结果保持不变。这四个用例基本覆盖了单行单列、无零、有零的所有极端结构。如果代码能在这四个用例上全部输出正确那基本可以保证边界逻辑没有问题了。还有一个技巧是如果矩阵中间有多个 0你可以测试一个L 形分布比如 0 在(1,1)和(2,2)这样最终应该只有第一行和第一列交叉出来的行列被置 0而其他位置保持不变。这种用例能有效检查你的标记阶段和清零阶段是否相互独立。5.3 一个隐蔽 bug更新顺序导致连锁反应最后再分享一个我实际调试时遇到过的隐性 bug。如果代码把根据标记置 0这一步写成了边扫描边修改而不是先统一标记再统一清零就会出现连锁反应。举个例子[1, 2, 3] [4, 0, 6] [7, 8, 9]在第一步扫描中(1,1)是 0我们标记了matrix[1][0] 0和matrix[0][1] 0。这没问题。但如果在第二步清零阶段我们遍历到(1,2)时先看到了matrix[1][0] 0所以把(1,2)置 0。这也没问题。但问题在于——第三步清零阶段之后如果代码又回去扫描第一行此时matrix[0][1] 0已经提前被我们标记了第一行本不该有 0 的现在有了如果你用第一行第一列再次作为依据去清零就会把原本不需要清零的位置也清零了。这个 bug 的根源是标记信息和清零结果被混在了一起。解决方案就是严格区分阶段——第一步只做标记第二步只做清零不能用清零的结果再去影响标记的判断。这也是为什么所有正确题解都会强调两次遍历的结构。在实际面试中如果你写出了遍历时遇到 0 立刻清零整行整列的写法不仅会连锁触发其他位置整个思路就直接错了。6. 进阶思路顺便了解一下带状态的一次遍历6.1 另一种实现风格的原理与取舍网上还有一种写法不用两个 bool 变量而是利用matrix[0][0]作为一个特殊标记额外再用一个col0变量记录第一列是否有 0。这个方案的核心差别在于它把第一行是否有 0的信息直接存在了matrix[0][0]上。大致的逻辑顺序是从第一行开始遍历用matrix[0][j]记录第 j 列是否需要清零用col0记录第一列是否需要清零。从第二行开始遍历用matrix[i][0]记录第 i 行是否需要清零。清零时从最后一行往前处理这样matrix[0][0]不会被提前覆盖。这个方案的代码通常短一些但理解和解释成本更高。因为它对matrix[0][0]的语义做了复用——它既可能是真实的原数据也可能表示第一行有零的标记信息取决于遍历到了哪个阶段。6.2 单变量方案的参考代码为了方便对比也贴一份这种解法的 Python 实现class Solution: def setZeroes(self, matrix: List[List[int]]) - None: m, n len(matrix), len(matrix[0]) col0 1 # 第一阶段标记 for i in range(m): if matrix[i][0] 0: col0 0 for j in range(1, n): if matrix[i][j] 0: matrix[i][0] 0 matrix[0][j] 0 # 第二阶段从后往前清零 for i in range(m - 1, -1, -1): for j in range(n - 1, 0, -1): if matrix[i][0] 0 or matrix[0][j] 0: matrix[i][j] 0 if col0 0: matrix[i][0] 0这个版本跑起来没问题但我个人觉得它没有双变量版本容易向面试官解释清楚。因为变量col0和matrix[0][0]之间的关系比较绕——matrix[0][0]本来是标记第一列的但它同时又被用作了标记第一行的存储位两个信息叠加在一个位置上的时候很容易把自己绕进去。6.3 面试和实战中推荐哪种在力扣上做题两种都能过但我强烈建议你用双变量版本。原因很简单代码正确性容易保证解释起来也不费劲。面试环境下面试官更看重的是你能否清晰表达思路而不是你能否写出最极致的精简代码。两个 bool 变量占用的空间是 O(1) 级别——准确地说就是两个常量——在渐进意义下依然符合题目的 O(1) 空间要求。O(1) 空间不代表零额外空间它只代表额外空间不随输入规模增长。两个布尔变量、一个整数变量这些都是允许的。很多人对这一点有误解以为 O(1) 就意味着一个变量都不能用其实完全不是这样。另外如果矩阵规模极大且元素类型是 32 位整数使用matrix[0][0]存特殊标记还有另一个隐患万一元素本身就有各种整数值你用特殊值来做标记就不可行。双变量方案的健壮性明显更好因为它完全不依赖矩阵元素的具体取值只依赖索引位置本身。7. 刷题心得与后续可扩展方向7.1 这道题在 Hot 100 里的定位Hot 100 这套题单前 20 题基本都是在帮你建立数组遍历 双指针/哈希表/原地操作这几个基础框架。矩阵置零恰好卡在这个位置它是从一维数组过渡到二维矩阵的一道桥梁题。做完这道题之后后面会碰到像螺旋矩阵旋转图像这类更侧重于高维数组遍历技巧的题那时你会发现二维矩阵下标之间的映射关系忽然变得异常重要。如果你也是按 Hot 100 顺序刷题的我的建议是这一题不要看过题解觉得自己懂了就跳过去一定自己独立写一遍最好把 O(mn) 和 O(1) 两个版本都写一遍。因为这道题的边界细节非常多只有亲手写出 bug 再修掉才能真正理解坐标系里行和列交叉的含义。7.2 矩阵类题目的通用分析框架借这道题我总结了一个刷矩阵类题目的分析框架后续做其他矩阵题时可以用第一先确认修改是 in-place 还是允许新矩阵。如果是 in-place就优先思考能不能复用原矩阵的某些行或列作为额外空间。第二再确认遍历顺序对结果有没有影响。矩阵置零这道题对遍历顺序本身不敏感但下一道题旋转图像就会因为遍历顺序不对导致值被覆盖。第三最后再考虑数据的取值范围看能不能用特殊值标记法。如果元素范围有限且已知特殊值法可以简化问题如果范围未知就不要碰这种技巧。这三个问题的答案决定了解题的总体方向。想想看如果我们一开始就不知道第一行第一列可以做标记数组这个技巧单纯靠遍历顺序优化是很难想到 O(1) 方案的——所以这类题的本质其实是对信息存储位置的敏感性考察。7.3 从算法到工程的迁移思考虽然矩阵置零是一个算法题但它在工程里确实有对应场景。比如图像处理中的透明像素处理——把图片里某个颜色值出现的位置所在的行列全部替换为透明色再比如表格处理软件中如果你选中某个包含公式错误的单元格软件可能会把整行整列标记出来方便你定位异常。这些场景的底层数据操作都和矩阵置零的思路高度一致。从面试角度看面试官其实并不是真的在乎你能不能把矩阵置零做出来他在乎的是你在面对空间受限的修改这个问题时有没有一套成体系的思路能不能先暴力的做出来再逐步优化能不能识别出哪些信息是必须保留的哪些信息可以复用现有存储。这种问题拆解能力远比记住某个题的特定解法值钱得多。每个人刷题的习惯不一样就我个人而言遇到这种中等偏简单的题我会刻意要求自己从暴力开始一步步优化到最优并记录每一步的复杂度和踩坑点。这样做的好处是在真正面试时我会更清楚我现在写的答案在什么水平而不是只会默写题解里的最优代码。希望大家也都能从这道题里得到启发刷题不只是为了 AC更是为了建立自己的思维路径。