刷 LeetCode 刷到矩阵专题时我一度觉得这些题有点“不讲武德”——看起来都是二维数组的操作真要动手写却各种边界错误、死循环。但刷完整理之后发现矩阵题其实是 Hot 100 里最值得花时间系统总结的一类它考察的不只是你会不会遍历而是你对坐标和状态的敏感度。这篇就聊聊我在 Hot 100 矩阵专题里的破题思路、代码细节和踩坑记录希望对正在刷题的朋友有帮助。先给不熟悉的朋友交个底Hot100 是一个高频题目合集基本覆盖了各大公司面试里最常见的算法题。矩阵专题是其中的类型标签之一常见题目包括矩阵置零、螺旋矩阵、旋转图像、搜索二维矩阵 II、岛屿数量、单词搜索、最大矩形等。这些题的数据结构一点也不复杂不需要高深的图论或者高级数据结构但每一道都在变着法子考验你对二维数组下标的掌控力。不信你可以做个测试随便拿一张 4x4 的方格纸在上面写下螺旋顺序的访问下标看看能不能不涂改地写到最后。我试过前几圈很顺到第三圈就开始出错——不是少了一个格子就是方向搞反了。矩阵题就难在这里逻辑上你完全知道该怎么做但转换成代码时下标计算的小偏差会让结果面目全非。1. 矩阵专题的整体认知与破题思路1.1 Hot100 里的矩阵题到底在考什么我刷下来最大的感受是矩阵专题的题目虽然形式上五花八门但核心考的就是三件事——坐标变换、状态标记和模式抽象。坐标变换对应的是“你在哪个位置、要往哪里走”状态标记对应的是“哪些信息需要记住、记在哪里”模式抽象对应的是“这个矩阵题本质是什么结构”。如果你把这三点记在心里再去看 Hot100 里的矩阵题就会发现自己能对题目做分类了。哪些题考坐标变换最重螺旋矩阵、旋转图像、对角线遍历。哪些题考状态标记最重矩阵置零、岛屿数量、单词搜索。哪些题考模式抽象最重搜索二维矩阵 II 本质上是一棵二叉搜索树最大矩形本质上是一维柱状图加单调栈。我自己整理过一张常见题目的考点速查表刷题时贴在笔记本旁边很有用题目核心考点关键技巧推荐复杂度矩阵置零状态标记第一行第一列作标记O(mn) 时间O(1) 空间螺旋矩阵坐标变换四边界收缩法O(mn) 时间O(1) 空间旋转图像坐标变换转置 行反转O(n^2) 时间O(1) 空间搜索二维矩阵 II模式抽象右上角出发排除法O(mn) 时间O(1) 空间岛屿数量状态标记DFS 原数组置零O(mn) 时间O(1) 空间单词搜索坐标变换 回溯方向数组 恢复现场O(mn*4^L) 时间O(L) 空间这张表不是让你背答案而是帮你建立题感看到一个矩阵题先判断它属于哪一类再去套对应模板。1.2 矩阵题背后的三类底层能力第一是坐标感知。矩阵的每个位置都由 row 和 col 唯一确定题目里的“第 i 行”“第 j 列”“沿对角线”“顺时针旋转”这些动作本质都是坐标变换。做这类题脑子里要有坐标系的画面感最好用手比划一下往右是 col 加一往下是 row 加一往左上就是 row 减一且 col 减一。别看这很简单螺旋矩阵、旋转图像、对角线遍历这些题一旦方向多了人就容易乱。第二是状态设计。很多矩阵题需要在遍历过程中记录一些状态比如哪些行要置零、哪些格子已经访问过、当前路径上哪些字母已经用掉。状态放在哪里、怎么更新、什么时候清除直接决定了空间复杂度和正确性。矩阵置零的 O(1) 解法就是把状态存进矩阵本身这是非常经典的状态设计案例。第三是模式抽象。有些矩阵题表面是二维数组本质是其他数据结构。最典型的是搜索二维矩阵 II——它的递增特性让矩阵变成了一棵隐形的二叉搜索树从右上角沿着“小往左、大往下”的规则走每一步都像是在二叉树上做判断。能看出这一层解题自然又快又稳。这种抽象能力是区分“背题”和“懂题”的分水岭。我认为刷矩阵专题的正确节奏应该是先理解这三类能力再分题型去练。不要一上来就背题解而是自己在纸上画矩阵一步步推演。矩阵题的规律基本都能在小纸片上推出来这比直接看代码要有效得多。2. 题型拆解四种高频套路2.1 原地操作矩阵置零的 O(1) 空间解法矩阵置零是矩阵专题的入门题也是考察“原地操作”的代表作。题目说如果 matrix[i][j] 等于 0就把第 i 行和第 j 列全部置成 0。一看到这种题很多人的第一反应是先遍历一遍把需要置零的行列记下来第二遍再统一置零。这自然是可行的用两个集合或者两个布尔数组就能实现空间复杂度 O(mn)。但如果面试官要求只用常数空间该怎么做答案是用矩阵的第一行和第一列充当标记数组。思路是先单独记住第一行和第一列本身是否含 0否则第一行第一列被标记覆盖后会失真然后遍历剩余区域遇到零就更新对应位置matrix[i][0] 0 表示第 i 行需要置零matrix[0][j] 0 表示第 j 列需要置零。标记完之后再根据这些标记统一置零最后单独处理第一行和第一列。这样额外空间只有两个布尔变量是 O(1)。这个小技巧的本质是把“额外存储”迁移到“矩阵自身未使用的信息载体”上。第一行和第一列在其他计算中是真实的元素但在这个问题里它们先被当作标记位用等所有标记做完了再恢复成普通行和列来处理。这里的顺序非常重要先处理非首行非首列的区域再处理首行首列否则标记会被后续置零操作干扰。我第一次写的时候就是先把第一行置零了结果后面扫描行列标记时全乱了白白调试了半个多小时。这种“用自身存状态”的思路在算法题里非常常见以后做并查集、状态压缩都会遇到。2.2 方向模拟螺旋矩阵的边界控制法螺旋矩阵是另一道经典题要求按顺时针螺旋顺序返回矩阵的所有元素。它的难点在于方向切换和边界收缩。我推荐维护四个边界变量top、bottom、left、right初始分别是 0、m-1、0、n-1。每次循环按“上边从左到右、右边从上到下、下边从右到左、左边从下到上”的顺序访问每访问完一条边就把对应的边界往里缩一格。看起来很直观但有一个细节容易翻车当矩阵只剩下中间一行或一列时走完上边和右边之后下边和左边的循环会和已经访问过的元素重复。解决办法是在访问下边之前判断 top bottom在访问左边之前判断 left right。这两个条件缺一不可。实际写代码时很多人会忘掉其中一个导致输出结果长度超过 m*n或者元素重复出现。我见过一个最隐蔽的 bug在非正方形矩阵里前半段正常后半段重复输出就是因为这两个判断少了一个。螺旋矩阵还有一个常见的变体是“螺旋矩阵 II”给定 n要求生成一个 1 到 n^2 的螺旋矩阵。解法思路完全一样只是把“输出”换成“填入”。万变不离其宗边界控制法是这类题的通用模板我建议把它背到滚瓜烂熟——面试里遇到原题容错率极高。2.3 技巧先行旋转图像与搜索二维矩阵 II旋转图像要求原地顺时针旋转 90 度。初学者容易写出一大堆坐标交换的代码稍不留神就错。最不容易出错的写法是两步法先沿主对角线转置再逐行反转。为什么这样是对的因为顺时针旋转 90 度等价于先做矩阵转置再水平翻转每一行。转置就是 matrix[i][j] 与 matrix[j][i] 互换水平翻转就是第 j 列与第 n-1-j 列互换。两步都是非常规则的操作写起来简单逻辑也好验证。如果题目改成逆时针旋转就改成“左右翻转再转置”或者“转置再垂直翻转”自己推导一遍就懂了。搜索二维矩阵 II则是典型的“模式抽象”题。矩阵的行列都是递增的暴力遍历是 O(mn)二分每行是 O(mlog n)但最优解是 O(mn) 的“右上角出发法”。从右上角 matrix[0][n-1] 开始当前值如果大于 target就向左移动一列因为下方只会更大如果小于 target就向下移动一行因为左侧只会更小相等就返回 true。整个流程和二叉搜索树的查找一模一样只是把左右子树换成了左右列和上下行。这里面的关键认知是不要把矩阵当成二维数组要把它看成二叉搜索树。一旦视角转换解法自然浮现。我对比过三种搜索方式的适用场景做成了一张小表方法时间复杂度空间复杂度适用场景暴力遍历O(mn)O(1)矩阵很小图省事每行二分O(m log n)O(1)只有行有序右上角排除O(mn)O(1)行列都递增最推荐2.4 网格遍历DFS/BFS 与访问标记矩阵专题里还有一大类题目核心是遍历网格岛屿数量、单词搜索、腐烂的橘子、被围绕的区域等等。这类题有一个通用模板每个位置有若干方向通常四个从起始位置出发沿着方向做深度优先或广度优先搜索同时标记访问状态防止死循环。标记状态有三种常见方式一是单独开一个布尔数组 visited二是把访问过的格子改成特殊值比如把 1 改成 0三是用方向数组配合边界检查。我个人更推荐第二种前提是题目允许修改原数组。它能把空间复杂度从 O(m*n) 降到 O(1)而且代码更短。比如岛屿数量里访问过的陆地直接改 0就不需要额外记录。但这里要特别注意回溯型的搜索比如单词搜索和状态遍历型的搜索比如岛屿数量对标记的处理是不同的。岛屿数量访问完一个格子它的状态就确定了直接改成 0 没问题单词搜索是在找一条路径这条路走不通时要回退所以访问标记必须在递归返回时恢复。我见过太多人把单词搜索写成“走过的格子再也走不回去”导致正确答案一条都搜不出来。恢复现场是回溯的精髓后面我会再展开讲。3. 核心题目拆解与代码实现3.1 矩阵置零从暴力到 O(1) 的完整演进先用最直观的方法复制一个临时矩阵遍历原矩阵遇到 0 就修改临时矩阵中对应的整行和整列。优点是思路简单缺点是空间 O(mn)肯定不是面试官想要的答案。进阶版用两个数组 rowZero 和 colZero 记录行和列是否需要置零空间 O(mn)。最终版就是上一节讲的标记法。我把完整代码贴出来注释标清楚每一步在干什么def setZeroes(matrix): if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[0]) # 1. 记录第一行、第一列本身是否含 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)) # 2. 用第一行和第一列作为标记位 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 # 3. 根据标记位把对应的行和列置零 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 # 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注意最前面的两个布尔变量。如果不记录它们当第一行本身有 0 时整个第一行会被标记位逻辑误处理成所有列都需要置零——因为 matrix[0][j] 在标记过程中都被写成了 0。这两个变量的作用是把第一行和第一列从标记系统中剥离出来留到最后单独处理。实际写代码时我发现一个更简洁的变体不单独记录 first_col_has_zero而是用列标记位和首列处理做微调。但简洁往往伴随可读性下降我面试时还是倾向于写上面这种直白版本。面试官要的是稳定正确不是炫技。3.2 螺旋矩阵标准模板和变体适配再贴一下我常用的螺旋矩阵模板。这个模板我用来解决过螺旋矩阵、螺旋矩阵 II以及按螺旋顺序遍历的其他变体稳定度很高def spiralOrder(matrix): res [] if not matrix or not matrix[0]: return res top, bottom 0, len(matrix) - 1 left, right 0, len(matrix[0]) - 1 while top bottom and left right: # 上边从左到右 for j in range(left, right 1): res.append(matrix[top][j]) top 1 # 右边从上到下 for i in range(top, bottom 1): res.append(matrix[i][right]) right - 1 # 下边从右到左需要判断边界是否仍有效 if top bottom: for j in range(right, left - 1, -1): res.append(matrix[bottom][j]) bottom - 1 # 左边从下到上同理需要判断 if left right: for i in range(bottom, top - 1, -1): res.append(matrix[i][left]) left 1 return res核心顺序上边、右边、下边、左边每完成一段就收缩对应边界。有人会问为什么外层循环已经写了 top bottom and left right内部还要重复判断因为在上边和右边走完后矩阵可能只剩一行一列此时如果继续走下边或左边会重复输出。这两个内部判断是防止越界和重复的关键务必保留。我踩过的坑是在写螺旋矩阵 II 时把 while 条件写成了 while count n * n然后再在里面逐段填数结果最后一个元素总是重复覆盖。后来发现根因还是边界判断顺序的问题——外层循环条件不变但内部某段循环已经越界。建议任何螺旋类题目都先画出最后两三圈的边界情况心里有数再写代码。画图真的比想代码快因为螺旋的边界变化是很机械的画一遍就记住了。3.3 旋转图像两步法为什么不容易错旋转图像我强烈推荐“转置 行反转”两步法def rotate(matrix): n len(matrix) # 第一步沿主对角线转置 for i in range(n): for j in range(i 1, n): matrix[i][j], matrix[j][i] matrix[j][i], matrix[i][j] # 第二步逐行反转 for i in range(n): matrix[i].reverse()这里的转置只需要遍历上三角j 从 i1 开始避免重复交换。行反转直接调 reverse。两步合起来就是顺时针 90 度旋转。逆时针旋转 90 度等价于先垂直翻转上下翻转再转置或者转置后逐列翻转。我会建议读者自己用 3x3 矩阵推一遍推导过程很简单但能让你彻底记住而不是死记硬背。推导时你只需要记录元素位置的变化比如 (0,0) 转 90 度后到 (0,2)两次变换正好落在预期位置。网上还有一种“环式旋转法”按层按组一次旋转四个元素比如 matrix[i][j] - matrix[j][n-1-i] - matrix[n-1-i][n-1-j] - matrix[n-1-j][i]。这种方法的优点是原地性更纯粹但下标关系容易算错我不太推荐新手一上来就写。面试中时间有限转置 反转的代码量更少且每个步骤都容易自测。我见过有同学在环式旋转法里把 n-1-i 写成 n-i整个旋转结果就乱了这种错误在紧张的时候特别容易犯。3.4 搜索二维矩阵 II右上角出发的查找def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) row, col 0, n - 1 # 从右上角出发 while row m and col 0: if matrix[row][col] target: return True elif matrix[row][col] target: col - 1 # 往左找更小的 else: row 1 # 往下找更大的 return False这段代码很短但背后的推理很关键右上角元素是它所在行的最大值、所在列的最小值。如果 target 比它小只能去左侧找如果比它大只能去下方找。每走一步就排除一整行或一整列虽然循环次数可能达到 mn但原因是排除法而非二分。这个题还有一个进阶版本搜索二维矩阵LeetCode 74矩阵的行有序且下一行的第一个元素大于上一行的最后一个元素相当于把整个矩阵展开成一个一维递增数组。解法就是标准二分查找把 mid 映射回 matrix[mid // n][mid % n]。Hot100 里通常考的是 240 这种行列各自递增的版本但两个题放在一起对比着看你会对“矩阵如何降维”有更深的理解。一个是“逐层排除”一个是“真正降维”面试时如果能主动把两者区分开会是一个不错的加分点。3.5 岛屿数量网格 DFS 的通用模板岛屿数量是网格遍历的入门题。思路遍历所有格子遇到陆地 1 就从这里开始 DFS把连通的陆地全部标记成已访问改成 0计数加一。代码模板def numIslands(grid): if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) count 0 def dfs(i, j): # 越界或遇到水就停止 if i 0 or i m or j 0 or j n or grid[i][j] 0: return grid[i][j] 0 # 标记为已访问 dfs(i 1, j) dfs(i - 1, j) dfs(i, j 1) dfs(i, j - 1) for i in range(m): for j in range(n): if grid[i][j] 1: count 1 dfs(i, j) return count这个模板可以应对大量网格类问题比如被围绕的区域改成从边界 DFS 标记不需要翻转的区域、腐烂的橘子改成 BFS 按分钟扩散、太平洋大西洋水流问题改成从两个方向的边界出发 DFS。每次遇到新题先判断它是“连通块计数”还是“路径搜索”前者用这种访问后直接改状态的模板就够了后者要记得恢复现场。不过要注意如果网格特别大DFS 递归深度可能超过 Python 默认的递归限制会报 RecursionError。这时候要么改用迭代栈模拟 DFS要么改用 BFS用队列要么用 sys.setrecursionlimit 调高限制。我在刷题平台上通常优先写 BFS毕竟自己维护队列比递归更可控也不怕递归层数太深。BFS 模板其实也很固定初始节点入队弹出时处理四个方向满足条件的入队并标记状态。真到了海量数据的场景这个习惯能帮你省掉不少麻烦。4. 常见问题与调试心得4.1 边界条件空矩阵与单行单列矩阵题最容易错的不是算法本身而是各种边界输入。空矩阵matrix []和空行matrix [[]]是两种不同的情况很多解法开头的 if not matrix or not matrix[0] 就是为了同时处理这两者。单行矩阵或单列矩阵在螺旋遍历、旋转、置零时都有特殊行为比如螺旋矩阵在只有一行时下边和左边的处理必须被跳过。我的习惯是写完核心逻辑后第一时间用四个用例自测——空矩阵、单行矩阵、单列矩阵、正常矩阵。这四个用例能过滤掉 80% 的边界错误。不要嫌麻烦很多矩阵题的隐蔽 bug 就是在单行单列这种极端输入下暴露出来的。比如旋转图像里 n1 时转置循环根本不执行直接返回即可但如果你的代码写了 n-1 这种下标就要小心越界。4.2 原地修改被覆盖的问题矩阵置零也好旋转图像也罢原地操作最大的隐患是“用到了还没被处理的值”。比如矩阵置零如果用拷贝矩阵的朴素思路就不会有覆盖问题一旦用标记法就必须先扫描、再统一置零不能在扫描的同时就改 matrix[i][j]因为后面的判断可能依赖原值。有一个相关技巧当需要借用矩阵自身存状态时尽量把状态写在第一行第一列而不是写在当前格子里。写在当前格子会导致遍历还没完成时状态已经乱了。这是我在实际编码中反复踩过的坑——比如写一个需要标记“已访问”的题直接把当前格改成 0结果后续的判断把 0 当成原来的状态处理了。这种错误特别容易在递归里出现因为递归的调用顺序是非线性的你很难一眼看出那个格子被提前改掉了。4.3 死循环与重复访问网格 DFS 如果忘了标记访问状态就会在两个格子之间无限递归A 访问 BB 又访问 A。这正是“死循环”最常见的来源。另一个常见来源是边界收缩后仍然访问已越界的区域。螺旋矩阵的重复输出本质上也是这一类问题。解决办法是在循环或递归的入口处先做越界和访问状态的检查再进入具体逻辑也就是“先判断再行动”的原则。排查这类问题我通常会在关键位置打印当前坐标和状态值print(i, j, grid[i][j])一旦看到某个坐标重复出现说明标记逻辑或边界收缩逻辑有问题。这一步放在代码里很丑但调试时极其有效定位之后再删掉就好。我调试网格 DFS 时还有一个土办法画一张小地图把访问过的格子一个个打勾递归跑完后看哪些格子没被勾到控制在 3x3 的范围里问题很快就能看出来。4.4 调试技巧学会打印整个矩阵矩阵题的输出结果肉眼很容易判断对错因为你对二维结构有直觉。调试的时候不要只看返回值要把中间状态的矩阵打印出来。比如螺旋矩阵每走完一条边就打印一次当前矩阵能清楚看到元素是否重复、边界是否正确收缩。对一个 4x4 的矩阵手动走一遍也就 16 个数字打印出来一目了然。我还有一个经验用自定义的小规模测试数据比如 3x3、4x4、5x6非正方形的矩阵分别跑一遍。非正方形矩阵能暴露很多你在正方形矩阵里发现不了的问题尤其是螺旋、对角线这类跟行列不对称有关的题目。正方形的特性会让很多对称性掩盖 bug换成非正方形就立刻现出原形。下面是常见问题速查表刷题时可以直接对照现象可能原因排查方法输出长度不等于 m*n螺旋循环少了边界判断检查 topbottom、leftright 两个判断部分格子没有置零标记位被后续操作覆盖检查标记扫描和统一置零是否分开DFS/递归栈溢出网格太大或没有正确标记改用 BFS 或检查访问标记旋转结果错乱转置下标写错用 3x3 矩阵手动推一遍回溯搜索找不到答案忘记恢复现场在递归返回前撤销 visited 标记5. 从刷题到工程矩阵能力的延伸价值5.1 混淆矩阵与机器学习中的矩阵思维刷题矩阵专题练出来的坐标和状态能力在工程里第一个用上的地方就是混淆矩阵。做分类模型评估时我们经常要算 TP、FP、FN、TN用 sklearn 的 confusion_matrix 一行就能出来但理解了矩阵的坐标语义你才能快速解释结果第 i 行第 j 列表示真实类别 i、预测类别 j 的样本数。很多数据分析和调参场景都需要你手动定位矩阵中某个格子的含义这种能力在刷题时已经不知不觉锻炼出来了。比如你在调二分类阈值想找个最优 cutoff用混淆矩阵的二维视角看其实就是沿着矩阵对角线搬移样本的分布。这种把问题抽象成矩阵坐标的思维方式和 LeetCode 里搜索二维矩阵时那种“沿着方向缩小范围”的思路本质上是一回事。我说矩阵题刷得好对数据科学有加分不是虚话。5.2 用 numpy 高效处理矩阵运算如果说 LeetCode 是在“养成手写矩阵逻辑的直觉”那工程里真正干活的往往是 numpy。求矩阵逆、特征值分解、矩阵乘法这些操作numpy 都有现成的高性能实现import numpy as np A np.array([[1, 2], [3, 4]]) A_inv np.linalg.inv(A) eigenvalues, eigenvectors np.linalg.eig(A) B np.dot(A, A_inv) # 约等于单位矩阵写这类代码时脑子里保留矩阵的 shape 意识非常重要——转置、广播、按轴求和每一步都要清楚结果是什么形状。很多数据科学的新手报 bug最后查出来都是 shape 对不上。这跟刷题时搞混 row 和 col 的道理一模一样。所以刷矩阵专题练出来的形状直觉放到工程里是实打实的加分项。你不需要背 numpy 的 API但你要是能一眼看出两个数组能不能直接相乘就知道 shape 匹配的规则是什么。5.3 矩阵思想在其他场景的体现矩阵思想最神奇的地方在于它无处不在。嵌入式里的矩阵键盘就是靠行线和列线的交叉来识别按键扫描逻辑本质是一个小的“状态矩阵”遍历图像处理里一张图就是一个二维像素矩阵卷积操作就是滑块在矩阵上移动甚至游戏开发里的地图寻路也把地图抽象成网格DFS/BFS 的模板直接就能用。矩阵键盘的场景我特别想多说一句按键识别中最怕“鬼键”问题当多个按键同时按下时行列扫描会产生误判硬件上一般加二极管或者用扫描法来避免。这个问题的本质就是在状态矩阵里同时出现了多个激活点你要设计一种遍历顺序让冲突尽可能少。这种工程直觉和你刷岛屿数量时遍历网格、标记状态的思路是同一个套路。所以说Hot100 矩阵专题刷的不只是几道题而是一整套“二维世界里的思考方式”。结尾刷完 Hot100 里的矩阵专题我自己最大的变化是看到任何二维数组题目不再下意识觉得繁琐而是先想清楚三个问题——坐标怎么走、状态怎么记、能不能抽象成更简单的结构。这三个问题背后其实就是我在前面反复强调的坐标感知、状态设计和模式抽象。矩阵题的代码量普遍不大真正的难点永远在动手写之前的那几十秒思考里。最后再分享一个小技巧我刷矩阵题时会准备一个固定的草稿本专门画 3x3 和 4x4 的矩阵格子。每道题的思路先在格子图上走一遍再转到代码。这个方法帮我少写了很多调试时间也让我对那些看似玄乎的下标变换有了真正的掌控感。如果你正卡在矩阵题上不妨试试这个方法。
