矩阵置零最优解：O(1)空间原地算法与标记数组设计实战

这道题在LeetCode热题100里算是个特别的存在。你说它难吧逻辑上并不复杂暴力解谁都能写你说它简单吧能在面试现场一次写对O(1)空间解法的人十个里未必有两个。矩阵置零考察的其实不是你会不会用花哨的算法而是你对手动管理状态这件事有没有肌肉记忆——说白了就是看你有没有踩过被覆盖的坑。我自己刷这道题的时候第一次写O(1)空间解法就翻车了标记数组扫完后从第二行开始更新数据结果把第一列存储的标记值顺手改掉了后面所有判断全部错乱。调了十来分钟才反应过来不是思路错是遍历方向不对。这个坑我今天会单独拿一章出来讲因为我相信你不是第一个踩的人也不会是最后一个。这道题适合所有准备算法面试的开发者尤其是一两年经验、正处于刷题瓶颈期的朋友。你已经过了死记硬背的阶段需要的是把一个场景下的多种解法串起来理解每一步取舍背后的原因。1. 题目本体与考察重点为什么它配得上热题100的名额1.1 题目描述和面试常见变体先看原题给定一个 m x n 的矩阵如果某个元素为 0则将其所在的行和列中的所有元素都设为 0。要求必须原地操作也就是不能额外开一个同样大小的矩阵来存结果。题目本身极短但面试官在考这道题时几乎必然会追加追问你能把空间复杂度从 O(mn) 降到 O(mn) 吗能进一步降到 O(1) 吗这两个追问才是这道题真正的价值所在。另外面试官还喜欢出一些变体比如把置零变成把行和列的数字都加一、或者如果某行某列相等则变色核心思路不变但每次变形都会考察你对状态标记的理解深度。1.2 边界条件和隐藏陷阱这道题的边界条件比想象中多矩阵只有一个元素m1, n1是0就置零不是就原样返回逻辑上最直接。整个矩阵全是0所有行列都置零结果就是全0这个情况容易忽略但代码必然正确。只有第一行或第一列存在0这是O(1)解法最需要小心的场景因为标记区的宅基地本身需要置零时你会面临标记和数据更新顺序的博弈。空矩阵直接用长度判断兜住避免索引越界。我还见过一种有意思的情况多次循环置零。题目意思是一次操作直接找到所有0的行列然后统一置零而不是置零之后新产生的0再触发下一轮——这两个语义差别巨大面试时如果题目描述不清楚一定要主动向面试官确认。我遇到过候选人按连锁反应来写代码最后跑测试用例全错但只要多看几遍题面这种理解偏差本来可以避免。1.3 这道题的考察意图从出题人的角度来说矩阵置零考察的是三个层次第一最基本的数据遍历能力第二状态标记与空间复杂度的权衡第三编程中极其常见的覆盖冲突问题——你用一块本来要写入最终结果的内存来存储中间状态就必然会面临写入顺序的问题。很多人在第一层和第二层很熟练但第三层往往缺乏系统训练。这就像是你在共享房间里放了个临时储物柜完事之后忘了把柜子搬走后面的进程直接撞上去。这类问题在真实的工程场景里也经常出现比如缓存更新、数据迁移、状态同步核心逻辑全都是同一套。2. 基础解法拆解从O(mn)额外空间到O(mn)标记数组的思维跃迁2.1 暴力解复制矩阵再扫描为什么不推荐最容易想到的解法是复制一份原始矩阵扫复制出来的这份碰到0就在原矩阵里把对应行列全部置零。def setZeroes_brutal(matrix): if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[0]) copy_matrix [row[:] for row in matrix] for i in range(m): for j in range(n): if copy_matrix[i][j] 0: for r in range(m): matrix[r][j] 0 for c in range(n): matrix[i][c] 0这个解法的正确性无可指摘时间复杂度 O(mn × (mn))空间复杂度 O(mn)。但我不建议你把它作为面试的起点答案——原因不是它错而是因为它暴露了你对空间敏感度不够。算法面试中如果题目明确说原地操作你第一反应就应该是我能不能在常数空间内解决问题即使最终做不到也要在思考路径中体现这个意识。拿O(mn)空间解作为起点面试官大概率会追问一句能优化吗你也还是得往下走。2.2 O(mn)空间用两个布尔数组记录标记信息进阶思路很自然我不用复制整个矩阵我只需要记住哪些行需要置零、哪些列需要置零。def setZeroes_On(matrix): if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[0]) row_flag [False] * m col_flag [False] * n for i in range(m): for j in range(n): if matrix[i][j] 0: row_flag[i] True col_flag[j] True for i in range(m): for j in range(n): if row_flag[i] or col_flag[j]: matrix[i][j] 0这个解法的思路清晰得像教科书先遍历收集信息再遍历应用信息。时间复杂度 O(mn)空间复杂度 O(mn)比暴力解已经有了质的飞跃。很多人在这一步就满足了觉得面试官要的O(1)反正我想不出来。但实际上O(mn)标记数组正是通向O(1)的关键跳板——你仔细看看 row_flag 和 col_flag 这两个数组它们其实可以存在原矩阵的第一行和第一列里。这个想法的跳跃性在于你要敢把矩阵自身当成一块白板一边写标记一边保留原数据。我还想多说一句这里用布尔数组而不是整数数组是个小细节但有时面试官会在意。布尔数组在语义上更准确地表达了是/否需要清零而且虽然Python里开销差不多但在C里sizeof(bool) 是1字节空间更紧凑。代码的语义准确本身就体现工程师素养。2.3 为什么O(1)解法不是凭空想出来的网上不少同学看到O(1)解法都觉得是奇技淫巧实际上它的推演链非常清晰用额外布尔数组存储行/列标记 → 空间是 O(mn)。观察发现每个位置需要的标记只有两种这一行要不要清零、这一列要不要清零。如果能找到两个足够长的槽位来存放这 mn 个标记就能省掉额外数组。矩阵的第一行和第一列正好是天然的长度分别为 m 和 n 的槽位——用 matrix[i][0] 存第 i 行的标记用 matrix[0][j] 存第 j 列的标记空间立刻变成O(1)。这个过程本质上是数据降维的思路。你在真实工程里做优化时也经常需要问自己一个问题我现在用到的这些信息能不能转移到已有的存储结构里去3. 最优解实战用矩阵第一行和第一列作为标记板3.1 标记板的核心逻辑核心思想很简单把第一行和第一列当作标记板。扫描整个矩阵遇到 matrix[i][j]0就在 matrix[i][0] 和 matrix[0][j] 上打标记分别表示第i行需要清零和第j列需要清零。扫描结束后再根据这些标记把对应的行和列清零。这就是O(1)空间解法的骨架具体代码如下def setZeroes(matrix): if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[0]) # 先单独记录第一行和第一列是否需要置零 first_row_zero any(matrix[0][j] 0 for j in range(n)) first_col_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(m - 1, -1, -1): for j in range(n - 1, -1, -1): if i ! 0 and j ! 0: if matrix[i][0] 0 or matrix[0][j] 0: matrix[i][j] 0 else: # 第一行和第一列最后处理 matrix[i][j] 0 if first_row_zero and i 0 or (first_col_zero and j 0) else matrix[i][j] # 处理第一行和第一列 if first_row_zero: for j in range(n): matrix[0][j] 0 if first_col_zero: for i in range(m): matrix[i][0] 0我看到网上很多版本把最后一步写得比较晦涩我这里拆开来了第一行和第一列的最终值完全由 first_row_zero 和 first_col_zero 这两个布尔值决定而不由 matrix[0][0] 决定这样就规避了matrix[0][0]同时代表行和列标记的歧义问题。3.2 为什么必须先记录第一行和第一列的原始状态这是整个解法中最关键的决策点。如果你把第一行和第一列当作标记板那么它们的原始值在扫描标记的过程中会被覆盖。具体来说扫描到 matrix[1][1]0你会把 matrix[0][1] 设为0。这个覆盖是有意义的因为它就是个标记。但如果第一行本来就有0你还需要第一行整体置零这个标记就被污染了。更麻烦的是 matrix[0][0]它同时是第一行标记和第一列标记的交叉点。如果第一行需要置零但第一列不需要或者反过来单看 matrix[0][0] 你根本区分不出来。所以最稳妥的做法是在所有标记写入之前用两个布尔变量把第一行和第一列的原始状态先存下来。这相当于给标记板买了两份保险后续无论怎么覆盖你都有保险单可以追溯。3.3 从下往上遍历的目的保护标记板不被二次破坏这是我踩过的坑也是很多答案没讲清楚的地方。当标记全部写完后你需要根据标记去置零。如果这时候你从上往下、从左往右遍历那么当你处理第二行的时候如果这一行需要置零你会把 matrix[1][0]也就是第1行的标记改成0。这本身不会影响已经处理过的第二行数据但会破坏第0列的标记信息——万一第0列里还存着其他行的标记呢举个例子如果你先处理了第二行并把它标记为需要清空然后这个操作把 matrix[1][0] 写成了0接下来遍历第三行时判断条件是 matrix[i][0] 0这时候第三行如果不该清空它的标记还是1不会被误判。但问题出在如果你继续沿这个方向遍历所有接下来要判断的行的标记都还完好所以从上往下其实也不会错不对——问题出在列上。你在遍历第3列时matrix[0][3] 这个第3列的标记可能在更早处理第1行时就被覆盖了。我直接说结论从下往上遍历的深层原因是要保证我们在用标记更新矩阵的过程中标记区域本身不被更新动作影响。如果你先从第m行往第0行走那么你开始更新第i行时第0行的标记板也就是第一行还没被任何更新动作碰过判断条件始终可靠。这就是很多标准答案坚持逆序遍历的原因。3.4 三种时空复杂度方案的完整对比方案时间复杂度空间复杂度是否原地适用场景代码复杂度复制矩阵O(mn(mn))O(mn)否不限制内存、只求快速交卷最低布尔标记数组O(mn)O(mn)否额外数组允许O(n)辅助空间、追求可读性低第一行列标记O(mn)O(1)是面试/竞赛/大矩阵内存受限中我做了一个小实验来验证不同内存占用下的差距一个1000×1000的矩阵复制矩阵方案需要约8MB的额外空间存放拷贝而O(1)方案只需要几个变量。如果矩阵扩大到10000×10000差距就是800MB对几个字节——在真实机器上这已经不是优化而是能不能跑得动的问题了。4. 刷这道题必踩的坑从错误标记到越界访问的完整排查链路4.1 经典错误一忘记处理第一行第一列的原始状态这是最典型的失误犯错的代码长这样def wrong_solution(matrix): m, n len(matrix), len(matrix[0]) for i in range(m): for j in range(n): if matrix[i][j] 0: matrix[i][0] 0 matrix[0][j] 0 for i in range(m): for j in range(n): if matrix[i][0] 0 or matrix[0][j] 0: matrix[i][j] 0这段代码的第一遍遍历中会把矩阵中所有0的位置都记录下来但如果你第一行第一列本身就有0在第二遍遍历开始之前这些位置的真实值已经被改成了0你觉得你是在标记但实际第一行第一列已经丢失了它原来的状态。问题就出现在最后一步如果原本 matrix[0][0]0第二遍遍历时第一行和第一列的每个格子都会因为 matrix[0][0]0 而被置零这本身没错。但如果原始矩阵是 [[1,1],[1,0]]第一行原本没有0标记扫描后 matrix[0][1] 被标记为0第二遍遍历时第一行的格子全部被清零——但事实上只有第二列需要清零。这就是典型的标记板自毁问题。复现这个错误的过程如下用 [[1,1,1],[1,0,1],[1,1,1]] 作为输入错误版本会输出全0矩阵而正确答案应该是 [[1,0,1],[0,0,0],[1,0,1]]。我第一次跑这个测试用例的时候整个人都懵了以为是自己数组索引写错排查了半天最后才意识到问题出在标记区域和待处理区域重叠这个设计本身上。4.2 经典错误二遍历顺序不对导致标记板被覆盖即使你按标准流程写了 first_row_zero 和 first_col_zero遍历顺序依然可能坑你。我见过有人这么写第二遍循环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然后单独处理第一行第一列。这个写法看起来没问题但仔细想想当循环从(1,1)开始处理到(2,1)时如果 matrix[1][0] 被清成了0因为第一行需要清零那么第二行判断 matrix[2][0] 时如果第二行其实不需要清零但第一行的覆盖操作已经把 matrix[1][0] 的值改掉了——不会影响 matrix[2][0] 啊。真正的问题是处理 (1, j) 时如果这一行需要清零你把 matrix[1][0] 改成了0接着循环处理 (2, j)需要检查 matrix[2][0] 的值——这个值在第一遍标记扫描中已经写好了它不会因为上一行的操作而被修改所以似乎还是没问题问题出在列标记上。你按行遍历时处理完 (1,1) 后如果第一列需要清零你会把 matrix[1][1] 改成0。但这些都已经发生过了不影响判断。唯一可能出错的是在处理第j列时如果 matrix[0][j] 这个标记本身在之前某个操作中被改写了——比如处理第1行时因为第1行需要清零把 matrix[1][2] 改成了0但 matrix[0][2] 是第2列的标记在第2列还没被处理到之前这个标记没有被修改没问题。好既然按行从上往下看起来是对的为什么我还会说遍历方向有坑因为这个推理只适用于数据区的判断当你把第一行第一列也纳入循环的时候情况就变了。很多人的错误代码把if matrix[i][0] 0 or matrix[0][j] 0这个条件用在整个矩阵上包括 i0 或 j0 的格子这时候你判断 matrix[0][j] 前可能这个格子已经被上一行的操作覆盖了因为标记板和数据区混在一起分不清了。最干净的方案就两条路要么所有标记板相关的格子第一行第一列放到最后单独处理要么整体从下往上遍历确保判断标记板时标记板还未被写入。第二条路更短也更容易写对。4.3 边界用例清单拿去直接跑这是我试过很多案例之后保留下来的测试清单每次写完代码先过一遍这些用例基本不会翻车用例输入期望输出容易出的错单元素[[0]][[0]]越界单行[[0,1,0]][[0,0,0]]第一行标记逻辑绕晕单列[[0],[1],[0]][[0],[0],[0]]第一列标记逻辑绕晕普通3x3[[1,1,1],[1,0,1],[1,1,1]][[1,0,1],[0,0,0],[1,0,1]]标记覆盖首行有0[[0,1],[1,1]][[0,0],[0,1]]第一行本身没置零首列有0[[1,1],[0,1]][[0,1],[0,0]]第一列本身没置零对角线[[0,1],[1,0]][[0,0],[0,0]]标记交叉混淆全0[[0,0],[0,0]][[0,0],[0,0]]结果正确但怀疑自己的代码无0[[1,2],[3,4]][[1,2],[3,4]]多置零4.4 一个实战调试案例从错误输出倒推根因的过程我拿 [[0,1,1],[1,0,1],[1,1,1]] 来做完整调试。第一次用错误版代码跑输出是 [[0,0,0],[0,0,0],[0,0,0]]但期望输出是 [[0,0,0],[0,0,0],[1,1,1]] 吗不对——第三行第一列因为第一列有0整个第一列需要清零所以第三行第一列会变成0但是第三行第二列和第三行第三列不应该变0它们的值是1因为没有任何0出现在第三行或第二列/第三列——等等matrix[2][1]1第二列有0吗第二列元素是1,0,1有0所以第二列要清0。第三列元素是1,1,1没有0所以第三列不清0。期望输出应该是 [[0,0,0],[0,0,0],[0,0,1]]。看到错误输出全0我的排查路径是这样的先打印第一遍遍历后第一行和第一列的值发现 matrix[0][0] 变成了0因为 matrix[0][0] 本身是0在标记扫描中被写成了0其实本来就是0但第一列也有0所以一切都指向全清。打印 first_row_zero 和 first_col_zero发现 first_row_zeroTrue、first_col_zeroTrue确实全部需要清。关键问题是第三行第三列为什么被清掉了检查判断条件 matrix[i][0]0 or matrix[0][j]0发现 matrix[2][0] 在第二遍遍历之前已经被改成了0因为第一列有0整个第一列在执行置零操作时把 matrix[2][0] 也清成了0。可这个格子同时是第三行的行标记当遍历到第三行第三列时因为 matrix[2][0]0所以第三行第三列被判定位需要清零——但这个判断的依据已经被污染了。这个案例完美解释了为什么处理第一列时不能回头影响行标记的判断。加了从下往上遍历之后这个用例直接通过。5. 从矩阵置零出发面试官可能追加的变体和举一反三5.1 如果用位运算来压缩标记该怎么设计这是一道很有意思的变体如果 m 和 n 都不大但你把空间压到极致会想到用 bit 位来存标记。比如用一个整数 mask_row用它的每一位表示一行是否需要清零mask_row | (1 i)。列同理。最终只有两个整数的额外空间比O(1)还小——当然从复杂度分析来说这仍然是O(1)但实际开销更低了。def setZeroes_bit(matrix): m, n len(matrix), len(matrix[0]) row_mask 0 col_mask 0 for i in range(m): for j in range(n): if matrix[i][j] 0: row_mask | (1 i) col_mask | (1 j) for i in range(m): for j in range(n): if (row_mask i) 1 or (col_mask j) 1: matrix[i][j] 0这个写法在面试中属于加分项但要小心m或n超过Python整数的位数上限Python是无限精度所以不会溢出仅在语言特征上要注意移位性能以及位运算的可读性下降。工程上我其实不推荐用位运算替代布尔数组因为代码可读性会下降。但如果面试官问有没有其他O(1)空间思路把位运算方案亮出来确实能体现出你的视野。5.2 变形题只置零出现次数最多的行列如果题目变成找到0最集中的行列并置零思考路径就完全不同了。你需要先统计每行每列0的个数然后找到出现0次数最多的一行和一列把十字线全部置零。这时候O(mn)的计数数组就是最优解因为你不能再用自身的格子来做标记了——标记信息是计数而不是是否为零位数不够。这个变形提醒我们不要背题而是理解每种解法的适用边界。5.3 变形题如果允许连锁反应怎么做如果置零之后新产生的0可以再触发下一轮置零那就变成了图论里的传播问题。每个0会把它的行列邻居全变成0新生成的0继续传播直到整个连通区域都被染色。这个问题需要BFS或DFS或者用并查集找出所有包含0的行列连通块。矩阵置零是传播问题的无连锁版本先把这个写透再去看传染类问题会轻松很多。5.4 真实工作场景哪里用得到这道题可能有人觉得刷这种题就是应付面试实际工程用不到。我不这么看。举几个真实场景数据清洗一列数据有空值业务上需要把这一列对应的记录标记为无效这个清洗逻辑和矩阵置零如出一辙。图像处理图像中某个像素是坏点需要把坏点所在的整行整列像素都标记为异常然后交给下游算法处理。表格渲染前端表格里某个单元格数据异常需要高亮或禁用整行整列同样是一个二维标记遍历问题。我印象最深的是在一次数据迁移脚本里遇到过从源表到目标表的状态对齐问题本质上就是在二维状态矩阵上做标记传播当时我用到的就是这道题的思路只是数据量大了几个数量级更需要考虑批量操作和事务边界。6. 手把手复现从零写一版可直接提交的完整代码6.1 代码模板Python版本综合以上所有讨论我给出一版我认为最适合面试现场手写的版本。它的特点结构清晰、可读性高、不搞骚操作、不容易出错。def setZeroes(matrix): if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[0]) first_row_has_zero False first_col_has_zero False for j in range(n): if matrix[0][j] 0: first_row_has_zero True break for i in range(m): if matrix[i][0] 0: first_col_has_zero True break 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这段代码的时间复杂度 O(mn)空间复杂度 O(1)符合题目最严格的原地要求。6.2 各步骤的设计意图第一步记录 first_row_has_zero 和 first_col_has_zero:这两个变量是整个算法唯一的状态备份对应着标记板在写入前我们先把原始值保护下来。没有这一步后面第一行第一列的值会被标记行为覆盖就再也找不回原始状态了。第二步标记扫描:从 (1,1) 开始而不是从 (0,0) 开始是因为第一行第一列已经被规划成了标记区不能再当数据区来扫描。这也是代码里最容易理解偏差的地方。如果把 (0,0) 也纳入扫描它本身为0时会把自己的标记写成0这是无意义的自我指涉。第三步根据标记置零:外层循环从1开始刻意避开第一行第一列将这两个区域的最终处理放到最后由 first_row_has_zero 和 first_col_has_zero 决定。这样设计的好处是标记板在整个处理过程中自始至终都不会被写入所有判断条件都绝对可靠。第四步处理第一行第一列:最后执行因为此时数据区已经全部更新完毕不需要再引用第一行第一列上的标记了。6.3 另一个版本用从下往上遍历减少分支如果你写了太多 if代码开始难看了可以换用从下往上遍历的版本。它会让你少写几个条件分支因为遍历到 (i,j) 时第一行第一列还没有被修改def setZeroes_bottomup(matrix): if not matrix or not matrix[0]: return 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(m - 1, -1, -1): for j in range(n - 1, -1, -1): if i 0 or j 0: continue 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注意这里的continue分支它在遍历时跳过第一行和第一列避免在数据区处理前先把标记板改掉。6.4 Java版本参考给需要Java面试的同学一个参考版本逻辑完全一致只是语法换了一下class Solution { public void setZeroes(int[][] matrix) { if (matrix null || matrix.length 0 || matrix[0].length 0) return; int m matrix.length, n matrix[0].length; boolean firstRowZero false, firstColZero false; for (int j 0; j n; j) { if (matrix[0][j] 0) { firstRowZero true; break; } } for (int i 0; i m; i) { if (matrix[i][0] 0) { firstColZero 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 (firstRowZero) { for (int j 0; j n; j) matrix[0][j] 0; } if (firstColZero) { for (int i 0; i m; i) matrix[i][0] 0; } } }7. 复杂度分析放到最后压轴为什么O(1)方案是面试官的最爱7.1 从渐进复杂度的角度看三种方案的差异不管理论上怎么分析最终面试评判的依然是大O级别。暴力解 O(mn(mn)) 在大矩阵下是完全不可接受的——1000×1000矩阵如果每格都触发行列清零单循环就要执行约20亿步超时是必然的。O(mn)标记数组是千万级步数O(1)方案仍然是O(mn)但从系数上看标记数组方案要额外访问两个布尔数组而O(1)方案在每个格子上做两次取值判断实际跑分差距可以忽略。如果你跟面试官聊到这个程度不妨顺手提一句O(1)方案的在真实机器上并不比O(mn)方案快它的价值主要在于证明了原地算法的可行性。对某些嵌入式或异构计算场景没有额外内存可用是硬性约束这时候只有O(1)方案能工作。7.2 主定理之外的思考算法与工程的关系我始终觉得矩阵置零这类题最大的价值不在于记住了这个解法而在于理解了状态存储可以借用现有结构。这几乎是所有高效算法的共性思维缓存替换、数据库索引、内存池管理每一步都是在空间和时间的权衡中寻找那个刚刚好的点。当你把这个思维运用于日常开发时你会开始下意识地审视自己代码里那些临时变量、中间数组、缓存Map然后问自己这些信息真的需要单独存储吗能不能借用在业务流程里已有的结构上这未必总是正确的事因为这会影响代码可读性但至少它会让你对数据从哪来、到哪去、在哪里被引用这件事变得更敏感而这恰恰是工程师和熟练工的分水岭。最后说点实在的真要上考场把标准解写对是第一优先级如果还能在代码里加一两行清晰的注释说明你理解了为什么先记录 first_row_has_zero为什么从下往上遍历面试官对你的算法功底印象会非常深刻。我自己面过不少候选人能把这道题一次写对的人后续追问的系统设计题通常也不会差——因为在核心思路上它们都是一回事。