1. 矩阵篇的整体思路与题型拆解矩阵类题目在 LeetCode Hot 100 中占比不算高但出镜率相当稳定属于“考逻辑多于考算法”的一类题。说白了矩阵就是一个二维数组但正因为多了一个维度很多一维数组里很自然的操作放到二维场景里就变得容易出错遍历方向搞乱、坐标越界、原地修改覆盖了后续需要的原值这些都是高频翻车点。我见过不少同学刷到这里会觉得很别扭明明看题解能看懂自己一写就废。核心原因不是代码能力差而是脑子里没有建立一套“二维坐标系”的思维方式。矩阵题的本质是坐标系操作你要随时知道当前在什么位置、下一步往哪个方向走、边界在哪里、哪些格子已经被处理过了。把这四件事想清楚矩阵题一大半的难度就消失了。从 Hot 100 的实际构成来看矩阵篇覆盖的题型大致可以分成三类第一类是遍历与顺序控制典型代表是螺旋矩阵、旋转图像这类题不考复杂算法考的是你对边界条件的敏感度第二类是状态标记与原地修改典型代表是矩阵置零核心难点在于如何在 O(1) 额外空间下完成标记还不能丢失原有信息第三类是利用矩阵自身性质进行搜索或转化典型代表是搜索二维矩阵、矩阵中的最长递增路径这类题往往会跟二分、DFS、动态规划结合难度梯度也相对更大。如果目光放长远一点矩阵题在真实面试里往往不只是考一道题本身考官更看重的是你面对一个陌生数据结构时能不能快速建立模型、拆解子问题、控制边界。所以刷矩阵篇我建议你不是背题而是把每一道题背后那个“二维操作模板”抽出来形成肌肉记忆。我不想一上来就给一堆题号和题解那样太像资料汇编了。我更想先带你建立一套处理矩阵问题的底层层逻辑看到题目先判断该用什么“走法”然后再谈具体实现。这套逻辑建立起来之后上面提到的三类题型你基本都能快速找到下手点。2. 四大高频题型的核心方法论与代码模板矩阵篇最值得花时间的是这四道题——矩阵置零、螺旋矩阵、旋转图像、搜索二维矩阵。它们分别代表了四种最核心的二维操作模型标记复用、边界收缩、坐标变换、坐标趋近。把这四个模型吃透Hot 100 矩阵篇的主干就算拿下了。2.1 矩阵置零第一行第一列当标记位题目要求很简单如果矩阵里某个元素是 0那么它所在的行和列全部置为 0。最容易想到的做法是开两个数组分别记录哪些行、哪些列需要清零但这样额外空间是 O(mn)。进阶要求是 O(1) 额外空间这时候就得动点脑筋了。核心思路是“标记复用”——用矩阵的第一行和第一列来充当记录数组。具体做法分三步走先扫描第一行和第一列用两个布尔变量记住它们自身原本是否包含 0然后从第二行第二列开始遍历剩下的区域只要遇到matrix[i][j] 0就把matrix[i][0]和matrix[0][j]置为 0相当于在边界上做标记最后根据这些边界标记把对应行和列整体清零再回头处理第一行和第一列。这里有一个特别容易踩的坑必须先处理第一行第一列的原始状态再去做标记。如果一上来就扫描全矩阵第一行第一列的原始信息就被覆盖掉了。我第一次写的时候没有单独记录结果第一行里原本有 0 的情况处理完边界之后整行数据全丢了排查了半天才发现是顺序问题。代码模板如下def setZeroes(self, matrix: List[List[int]]) - None: 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(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_zero: for j in range(n): matrix[0][j] 0 if first_col_zero: for i in range(m): matrix[i][0] 0这段代码里清零的过程我建议从第二行第二列开始不要动标记本身所在的第一行和第一列否则会出现“清了标记导致后续判断失效”的连锁问题。这个问题在面试里经常被拿来追问答上来就是加分项。2.2 螺旋矩阵四指针边界收缩法螺旋矩阵这道题与其说是算法题不如说是“操作契约题”。你只需要按“右、下、左、上”的顺序一圈一圈往里走每走完一条边就把对应的边界往里缩一格直到所有元素都被访问过。我自己的写法是用四个变量top, bottom, left, right维护当前未遍历区域的边界然后在一个while循环里执行四次遍历。这里最关键的点是每次遍历完都要检查边界是否已经交错一旦top bottom或者left right立即退出循环否则单行或单列的矩阵会重复读取元素。比如上面一行往右走完top 1此时如果top bottom说明矩阵已经全走完了下面那几步就直接不用执行了。很多人的实现会在这里报IndexError就是因为单行矩阵往下走的时候边界检查做晚了。def spiralOrder(self, matrix: List[List[int]]) - List[int]: 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 or left right: break # 向左遍历下边界 for j in range(right, left - 1, -1): res.append(matrix[bottom][j]) bottom - 1 # 向上遍历左边界 for i in range(bottom, top - 1, -1): res.append(matrix[i][left]) left 1 return res这套四指针边界收缩的模板本身就是一个非常通用的二维模型。后面遇到任何“按层处理矩阵”的题都可以直接复用。还有一个变体是逆时针螺旋写法完全一样只要把四个方向的顺序反过来就行。2.3 旋转图像两次轴对称替代一次旋转旋转 90 度这道题如果直接按坐标去搬元素很容易把自己绕晕因为一个元素移动之后会连锁影响四个位置。业界最常用的技巧是先转置再左右翻转两步合起来就是顺时针旋转 90 度。从数学上讲转置交换了行列坐标左右翻转再反转列序两者的复合效果恰好等价于旋转。具体来说第一步把matrix[i][j]和matrix[j][i]交换遍历范围只需要上半三角第二步把每一行的元素以中线为轴左右对调。两步操作都是按行独立进行的逻辑简单而且不容易出错。def rotate(self, matrix: List[List[int]]) - None: 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()为什么我不建议直接硬算旋转坐标因为直接旋转的坐标映射是(i, j) - (j, n-1-i)中间需要额外的临时变量维护很容易做重或漏做。而转置加翻转的每步操作非常直观现场写代码几乎不会出错面试时也更容易讲清楚逻辑。顺带说一句如果是逆时针旋转 90 度做法是先上下翻转再转置顺序别搞反了。2.4 搜索二维矩阵从右上角开始走搜索二维矩阵在 Hot 100 里有两个版本一个是完全有序的矩阵每行每列均递增另一个是每行有序、每行第一个元素大于上一行最后一个元素本质退化成了一维有序数组的二分搜索。后者用二分就能解决重点说一下前者。每行每列都递增这个性质非常特殊它意味着从矩阵的右上角看出去向左的所有元素都比当前值小向下的所有元素都比当前值大。于是这里天然形成了一条“二分决策路径”目标值比当前元素小就往左走目标值比当前元素大就往下走。每一步都能排除一整行或一整列最坏情况下总共走 mn 步复杂度 O(mn)。def searchMatrix(self, matrix: List[List[int]], target: int) - bool: if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) i, j 0, n - 1 # 从右上角出发 while i m and j 0: if matrix[i][j] target: return True elif matrix[i][j] target: j - 1 # 当前值太大往左 else: i 1 # 当前值太小往下 return False这个“角点起步”的思路实际上是一种贪心式的坐标趋近模型。顺着这个模型还能推导出很多变体比如从左下角出发也可以只是判断方向要反过来。面试时如果考官追问“还能怎么优化”可以从右上角思路延伸到二分但不要画蛇添足先把基本解法讲清楚才有讨论空间。3. 经典真题复盘与代码实现细节前面四种模型属于矩阵篇的“基本功”真正能拉开差距的是把二维模型和更深的算法结合起来。这一节我挑两道覆盖面广、面试出现频率也比较高的题来完整复盘一道考图的连通性一道考降维思维。3.1 被围绕的区域从边界反向遍历这道题的核心难点不在于 DFS 本身而在于它的正向思维是陷阱。如果直接从内部的 O 出发去判断是否被 X 包围你必须对每个 O 做一次全连通检查然后还要回溯修改非常复杂。但换个角度想所有没有被 X 包围的 O一定是从边界上的 O 出发能连通到的。换句话说先找出边界相连的 O 并保护起来剩下的 O 就必然是包围的直接改掉就好。我在落地时用了“染色标记法”先从边界上的每一个 O 出发 DFS把能连通到的 O 临时标记成#全部标记完之后再遍历全矩阵遇到#就还原成O遇到残留的O就替换成X。这个思路简洁可靠而且只做一次全局遍历加若干次方向 DFS时间上是最优的。def solve(self, board: List[List[str]]) - None: if not board or not board[0]: return m, n len(board), len(board[0]) def dfs(i, j): if i 0 or i m or j 0 or j n or board[i][j] ! O: return board[i][j] # dfs(i - 1, j) dfs(i 1, j) dfs(i, j - 1) dfs(i, j 1) # 从边界出发标记所有可连通的 O for i in range(m): dfs(i, 0) dfs(i, n - 1) for j in range(n): dfs(0, j) dfs(m - 1, j) # 统一替换 for i in range(m): for j in range(n): if board[i][j] #: board[i][j] O elif board[i][j] O: board[i][j] X这道题如果矩阵规模很大递归 DFS 有爆栈风险商业产品里我建议改成显式栈的迭代 DFS。面试时写递归版本没问题但如果面试官问“矩阵特别大怎么办”能答出“递归转显式栈或 BFS”就是加分点。还有一个小细节DFS 的递归里我先判断board[i][j] ! O而不是 O这样可以省掉独立的 visited 数组用就地标记解决了“哪些格子访问过”的问题。3.2 最大矩形矩阵降维成柱状图最大矩形是矩阵篇里综合难度较高的一道题但它本质上是一个经典的降维问题逐行累积“当前格子往上连续有多少个 1”然后就变成了“每一行的柱状图里找最大矩形面积”也就是 LeetCode 84 题。84 题用单调栈求最大矩形面积是模板级解法O(n)外层再套一层行遍历总体 O(m * n)。我第一次做这题的时候没有想通降维这件事自己硬写了一个二维滑动窗口边界判断多到崩溃。后来把“每一行的高度数组”打出来看瞬间就明白了上一行的高度如果当前行是 0 就要清零否则高度加一。这个累积过程本身就是动态规划只是它藏得比较浅。单调栈部分的代码是核心def maximalRectangle(self, matrix: List[List[str]]) - int: if not matrix or not matrix[0]: return 0 m, n len(matrix), len(matrix[0]) heights [0] * n max_area 0 for i in range(m): for j in range(n): if matrix[i][j] 1: heights[j] 1 else: heights[j] 0 stack [] # 加入哨兵简化收尾处理 for k in range(n 1): cur heights[k] if k n else 0 while stack and heights[stack[-1]] cur: h heights[stack.pop()] left stack[-1] if stack else -1 area h * (k - left - 1) max_area max(max_area, area) stack.append(k) return max_area这里有一个实用技巧在柱状图数组末尾加一个高度为 0 的“哨兵柱”这样遍历结束后栈里剩余的元素能自动完成出栈结算不需要再写一个 while 循环单独处理栈内残余。很多题解里没有这一步导致代码里要多一段很丑的收尾逻辑。我强烈建议你把哨兵技巧记下来因为它在很多栈相关的算法里都通用。3.3 拓展二维前缀和快速求子矩阵和除了上面两道矩阵篇还经常出现一类“求子矩阵和、子矩阵最大和”的问题它们的通用预处理手段是二维前缀和。二维前缀和数组pre[i][j]表示从(0,0)到(i,j)围成矩形区域的所有元素之和递推公式是pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i][j]。这里多减一次pre[i-1][j-1]是因为左上方那部分被加了两次需要抵消。有了前缀和数组任意子矩阵(r1,c1)到(r2,c2)的和就能在 O(1) 时间内求出。虽然 Hot 100 矩阵篇里直接出前缀和的题目不算多但很多后续的难题比如动态规划优化、二维滑动窗口都会默认你知道这个技巧。提前备好后面刷题会轻松很多。4. 矩阵题的刷题顺序与避坑指南这个部分是我最想跟你分享的。刷题刷多了你会发现矩阵题的套路其实非常有限真正决定你能不能写出满分代码的往往是一些容易被忽略的边界细节和代码习惯。4.1 我认为最高效的刷题顺序如果你打算集中刷矩阵篇按下面这个顺序来效率最高先刷矩阵置零和螺旋矩阵这两道题能帮你建立“二维坐标感”和“边界控制感”然后刷旋转图像掌握坐标变换模型接着刷搜索二维矩阵理解如何利用矩阵有序性优化搜索再刷被围绕的区域和岛屿数量练习 DFS/BFS 与二维 visited 的各种标记方案最后挑战最大矩形体会降维思维在矩阵题中的威力。这样安排的原因很简单前几道题是模板后面的题是模板的组合或者升级。基础没打牢就冲最大矩形大概率会在“降维”这一步卡很久。我见过不少人是反过来刷的先做最大矩形做不出来心态崩了回头才发现前面的基础题都没吃透。4.2 高频报错点与边界条件速查表根据我自己的刷题记录和帮别人 review 代码的经验矩阵题的高频错误基本集中在下面几个位置我整理成了一张表常见错误出现的题型根因分析解决方案解决方案行和列的下标搞混所有矩阵题坐标轴意识不强把matrix[i][j]当成行列都对每次循环前先确认 i 是行还是 j 是行或直接改名row, col单行矩阵读取越界螺旋矩阵遍历完一行后没有及时检查边界每次收缩边界后立刻判断top bottom或left right遍历范围多算了半圈旋转图像/转置双层循环范围写成了全矩阵只遍历上半三角即j从i1开始原地修改导致原始值丢失矩阵置零用原矩阵存储标记时覆盖了信息标记区和数据区分离或者从右下角开始处理DFS 死循环被围绕的区域/岛屿数量缺少 visited 标记或标记时机不对在入栈/入队前就标记不要等到出栈才标记柱状图栈底残余未处理最大矩形循环结束没有清空单调栈数组后追加哨兵 0让所有元素自然结算4.3 面试现场的讲题节奏建议矩阵题在面试里通常不难能让考官眼前一亮的不是你写出正确答案而是你展现出的结构化拆解能力。我在面试别人和模拟面试的时候比较认可这样一套表达节奏拿到题先不要急着写代码用 30 秒到 1 分钟说清楚“我看到一个二维矩阵题敏感点是边界处理和状态标记。我的第一反应是用 XX 模型来处理最坏时间复杂度是 XX额外空间是 XX”。然后边说边写。以旋转图像为例比较好的表述是“这题我不用直接旋转坐标先转置再左右翻转两步都是二维数组的线性操作不会互相干扰。转置时只遍历上半三角避免重复交换。整体时间复杂度 O(n^2)额外空间 O(1)。”这段话一说出来考官就知道你平时做题确实总结过印象分会提高不少。还有一个我个人的小习惯面试时写矩阵题的循环边界先在草稿纸上标一遍“这个 range 的起点和终点”不要急着下笔。很多边界错误在写循环之前就能被消除值得花那十几秒。另外如果你的解法里出现了不止一个嵌套循环每层循环尽量用带语义的变量名row, col, top, bottom, left, right不要清一色用i, j。矩阵题很容易因为 i 和 j 的意义在不同代码段里发生变化而出错清晰命名能帮你自己和读你代码的人少受折磨。最后再多说一句。矩阵题刷到后面你会发现它们考察的并不是高深的数学而是“确定性问题”——确定下一步往哪走、确定哪些格子已经处理、确定状态之间如何转换。这类能力在真实开发里也非常有用因为所有二维表格、网格地图、图像像素的操作本质上都是矩阵操作。把这几道题刷扎实你练到的不仅是面试技巧还有处理复杂二维数据结构的底层功底。以后遇到再大的网格问题心里有了模型下手就不慌了。 
长河君 · 2026/10/10 4:20:37 · 阅读 1.2k LeetCode矩阵题全攻略：从边界控制到降维思维
1. 矩阵篇的整体思路与题型拆解矩阵类题目在 LeetCode Hot 100 中占比不算高但出镜率相当稳定属于“考逻辑多于考算法”的一类题。说白了矩阵就是一个二维数组但正因为多了一个维度很多一维数组里很自然的操作放到二维场景里就变得容易出错遍历方向搞乱、坐标越界、原地修改覆盖了后续需要的原值这些都是高频翻车点。我见过不少同学刷到这里会觉得很别扭明明看题解能看懂自己一写就废。核心原因不是代码能力差而是脑子里没有建立一套“二维坐标系”的思维方式。矩阵题的本质是坐标系操作你要随时知道当前在什么位置、下一步往哪个方向走、边界在哪里、哪些格子已经被处理过了。把这四件事想清楚矩阵题一大半的难度就消失了。从 Hot 100 的实际构成来看矩阵篇覆盖的题型大致可以分成三类第一类是遍历与顺序控制典型代表是螺旋矩阵、旋转图像这类题不考复杂算法考的是你对边界条件的敏感度第二类是状态标记与原地修改典型代表是矩阵置零核心难点在于如何在 O(1) 额外空间下完成标记还不能丢失原有信息第三类是利用矩阵自身性质进行搜索或转化典型代表是搜索二维矩阵、矩阵中的最长递增路径这类题往往会跟二分、DFS、动态规划结合难度梯度也相对更大。如果目光放长远一点矩阵题在真实面试里往往不只是考一道题本身考官更看重的是你面对一个陌生数据结构时能不能快速建立模型、拆解子问题、控制边界。所以刷矩阵篇我建议你不是背题而是把每一道题背后那个“二维操作模板”抽出来形成肌肉记忆。我不想一上来就给一堆题号和题解那样太像资料汇编了。我更想先带你建立一套处理矩阵问题的底层层逻辑看到题目先判断该用什么“走法”然后再谈具体实现。这套逻辑建立起来之后上面提到的三类题型你基本都能快速找到下手点。2. 四大高频题型的核心方法论与代码模板矩阵篇最值得花时间的是这四道题——矩阵置零、螺旋矩阵、旋转图像、搜索二维矩阵。它们分别代表了四种最核心的二维操作模型标记复用、边界收缩、坐标变换、坐标趋近。把这四个模型吃透Hot 100 矩阵篇的主干就算拿下了。2.1 矩阵置零第一行第一列当标记位题目要求很简单如果矩阵里某个元素是 0那么它所在的行和列全部置为 0。最容易想到的做法是开两个数组分别记录哪些行、哪些列需要清零但这样额外空间是 O(mn)。进阶要求是 O(1) 额外空间这时候就得动点脑筋了。核心思路是“标记复用”——用矩阵的第一行和第一列来充当记录数组。具体做法分三步走先扫描第一行和第一列用两个布尔变量记住它们自身原本是否包含 0然后从第二行第二列开始遍历剩下的区域只要遇到matrix[i][j] 0就把matrix[i][0]和matrix[0][j]置为 0相当于在边界上做标记最后根据这些边界标记把对应行和列整体清零再回头处理第一行和第一列。这里有一个特别容易踩的坑必须先处理第一行第一列的原始状态再去做标记。如果一上来就扫描全矩阵第一行第一列的原始信息就被覆盖掉了。我第一次写的时候没有单独记录结果第一行里原本有 0 的情况处理完边界之后整行数据全丢了排查了半天才发现是顺序问题。代码模板如下def setZeroes(self, matrix: List[List[int]]) - None: 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(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_zero: for j in range(n): matrix[0][j] 0 if first_col_zero: for i in range(m): matrix[i][0] 0这段代码里清零的过程我建议从第二行第二列开始不要动标记本身所在的第一行和第一列否则会出现“清了标记导致后续判断失效”的连锁问题。这个问题在面试里经常被拿来追问答上来就是加分项。2.2 螺旋矩阵四指针边界收缩法螺旋矩阵这道题与其说是算法题不如说是“操作契约题”。你只需要按“右、下、左、上”的顺序一圈一圈往里走每走完一条边就把对应的边界往里缩一格直到所有元素都被访问过。我自己的写法是用四个变量top, bottom, left, right维护当前未遍历区域的边界然后在一个while循环里执行四次遍历。这里最关键的点是每次遍历完都要检查边界是否已经交错一旦top bottom或者left right立即退出循环否则单行或单列的矩阵会重复读取元素。比如上面一行往右走完top 1此时如果top bottom说明矩阵已经全走完了下面那几步就直接不用执行了。很多人的实现会在这里报IndexError就是因为单行矩阵往下走的时候边界检查做晚了。def spiralOrder(self, matrix: List[List[int]]) - List[int]: 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 or left right: break # 向左遍历下边界 for j in range(right, left - 1, -1): res.append(matrix[bottom][j]) bottom - 1 # 向上遍历左边界 for i in range(bottom, top - 1, -1): res.append(matrix[i][left]) left 1 return res这套四指针边界收缩的模板本身就是一个非常通用的二维模型。后面遇到任何“按层处理矩阵”的题都可以直接复用。还有一个变体是逆时针螺旋写法完全一样只要把四个方向的顺序反过来就行。2.3 旋转图像两次轴对称替代一次旋转旋转 90 度这道题如果直接按坐标去搬元素很容易把自己绕晕因为一个元素移动之后会连锁影响四个位置。业界最常用的技巧是先转置再左右翻转两步合起来就是顺时针旋转 90 度。从数学上讲转置交换了行列坐标左右翻转再反转列序两者的复合效果恰好等价于旋转。具体来说第一步把matrix[i][j]和matrix[j][i]交换遍历范围只需要上半三角第二步把每一行的元素以中线为轴左右对调。两步操作都是按行独立进行的逻辑简单而且不容易出错。def rotate(self, matrix: List[List[int]]) - None: 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()为什么我不建议直接硬算旋转坐标因为直接旋转的坐标映射是(i, j) - (j, n-1-i)中间需要额外的临时变量维护很容易做重或漏做。而转置加翻转的每步操作非常直观现场写代码几乎不会出错面试时也更容易讲清楚逻辑。顺带说一句如果是逆时针旋转 90 度做法是先上下翻转再转置顺序别搞反了。2.4 搜索二维矩阵从右上角开始走搜索二维矩阵在 Hot 100 里有两个版本一个是完全有序的矩阵每行每列均递增另一个是每行有序、每行第一个元素大于上一行最后一个元素本质退化成了一维有序数组的二分搜索。后者用二分就能解决重点说一下前者。每行每列都递增这个性质非常特殊它意味着从矩阵的右上角看出去向左的所有元素都比当前值小向下的所有元素都比当前值大。于是这里天然形成了一条“二分决策路径”目标值比当前元素小就往左走目标值比当前元素大就往下走。每一步都能排除一整行或一整列最坏情况下总共走 mn 步复杂度 O(mn)。def searchMatrix(self, matrix: List[List[int]], target: int) - bool: if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) i, j 0, n - 1 # 从右上角出发 while i m and j 0: if matrix[i][j] target: return True elif matrix[i][j] target: j - 1 # 当前值太大往左 else: i 1 # 当前值太小往下 return False这个“角点起步”的思路实际上是一种贪心式的坐标趋近模型。顺着这个模型还能推导出很多变体比如从左下角出发也可以只是判断方向要反过来。面试时如果考官追问“还能怎么优化”可以从右上角思路延伸到二分但不要画蛇添足先把基本解法讲清楚才有讨论空间。3. 经典真题复盘与代码实现细节前面四种模型属于矩阵篇的“基本功”真正能拉开差距的是把二维模型和更深的算法结合起来。这一节我挑两道覆盖面广、面试出现频率也比较高的题来完整复盘一道考图的连通性一道考降维思维。3.1 被围绕的区域从边界反向遍历这道题的核心难点不在于 DFS 本身而在于它的正向思维是陷阱。如果直接从内部的 O 出发去判断是否被 X 包围你必须对每个 O 做一次全连通检查然后还要回溯修改非常复杂。但换个角度想所有没有被 X 包围的 O一定是从边界上的 O 出发能连通到的。换句话说先找出边界相连的 O 并保护起来剩下的 O 就必然是包围的直接改掉就好。我在落地时用了“染色标记法”先从边界上的每一个 O 出发 DFS把能连通到的 O 临时标记成#全部标记完之后再遍历全矩阵遇到#就还原成O遇到残留的O就替换成X。这个思路简洁可靠而且只做一次全局遍历加若干次方向 DFS时间上是最优的。def solve(self, board: List[List[str]]) - None: if not board or not board[0]: return m, n len(board), len(board[0]) def dfs(i, j): if i 0 or i m or j 0 or j n or board[i][j] ! O: return board[i][j] # dfs(i - 1, j) dfs(i 1, j) dfs(i, j - 1) dfs(i, j 1) # 从边界出发标记所有可连通的 O for i in range(m): dfs(i, 0) dfs(i, n - 1) for j in range(n): dfs(0, j) dfs(m - 1, j) # 统一替换 for i in range(m): for j in range(n): if board[i][j] #: board[i][j] O elif board[i][j] O: board[i][j] X这道题如果矩阵规模很大递归 DFS 有爆栈风险商业产品里我建议改成显式栈的迭代 DFS。面试时写递归版本没问题但如果面试官问“矩阵特别大怎么办”能答出“递归转显式栈或 BFS”就是加分点。还有一个小细节DFS 的递归里我先判断board[i][j] ! O而不是 O这样可以省掉独立的 visited 数组用就地标记解决了“哪些格子访问过”的问题。3.2 最大矩形矩阵降维成柱状图最大矩形是矩阵篇里综合难度较高的一道题但它本质上是一个经典的降维问题逐行累积“当前格子往上连续有多少个 1”然后就变成了“每一行的柱状图里找最大矩形面积”也就是 LeetCode 84 题。84 题用单调栈求最大矩形面积是模板级解法O(n)外层再套一层行遍历总体 O(m * n)。我第一次做这题的时候没有想通降维这件事自己硬写了一个二维滑动窗口边界判断多到崩溃。后来把“每一行的高度数组”打出来看瞬间就明白了上一行的高度如果当前行是 0 就要清零否则高度加一。这个累积过程本身就是动态规划只是它藏得比较浅。单调栈部分的代码是核心def maximalRectangle(self, matrix: List[List[str]]) - int: if not matrix or not matrix[0]: return 0 m, n len(matrix), len(matrix[0]) heights [0] * n max_area 0 for i in range(m): for j in range(n): if matrix[i][j] 1: heights[j] 1 else: heights[j] 0 stack [] # 加入哨兵简化收尾处理 for k in range(n 1): cur heights[k] if k n else 0 while stack and heights[stack[-1]] cur: h heights[stack.pop()] left stack[-1] if stack else -1 area h * (k - left - 1) max_area max(max_area, area) stack.append(k) return max_area这里有一个实用技巧在柱状图数组末尾加一个高度为 0 的“哨兵柱”这样遍历结束后栈里剩余的元素能自动完成出栈结算不需要再写一个 while 循环单独处理栈内残余。很多题解里没有这一步导致代码里要多一段很丑的收尾逻辑。我强烈建议你把哨兵技巧记下来因为它在很多栈相关的算法里都通用。3.3 拓展二维前缀和快速求子矩阵和除了上面两道矩阵篇还经常出现一类“求子矩阵和、子矩阵最大和”的问题它们的通用预处理手段是二维前缀和。二维前缀和数组pre[i][j]表示从(0,0)到(i,j)围成矩形区域的所有元素之和递推公式是pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i][j]。这里多减一次pre[i-1][j-1]是因为左上方那部分被加了两次需要抵消。有了前缀和数组任意子矩阵(r1,c1)到(r2,c2)的和就能在 O(1) 时间内求出。虽然 Hot 100 矩阵篇里直接出前缀和的题目不算多但很多后续的难题比如动态规划优化、二维滑动窗口都会默认你知道这个技巧。提前备好后面刷题会轻松很多。4. 矩阵题的刷题顺序与避坑指南这个部分是我最想跟你分享的。刷题刷多了你会发现矩阵题的套路其实非常有限真正决定你能不能写出满分代码的往往是一些容易被忽略的边界细节和代码习惯。4.1 我认为最高效的刷题顺序如果你打算集中刷矩阵篇按下面这个顺序来效率最高先刷矩阵置零和螺旋矩阵这两道题能帮你建立“二维坐标感”和“边界控制感”然后刷旋转图像掌握坐标变换模型接着刷搜索二维矩阵理解如何利用矩阵有序性优化搜索再刷被围绕的区域和岛屿数量练习 DFS/BFS 与二维 visited 的各种标记方案最后挑战最大矩形体会降维思维在矩阵题中的威力。这样安排的原因很简单前几道题是模板后面的题是模板的组合或者升级。基础没打牢就冲最大矩形大概率会在“降维”这一步卡很久。我见过不少人是反过来刷的先做最大矩形做不出来心态崩了回头才发现前面的基础题都没吃透。4.2 高频报错点与边界条件速查表根据我自己的刷题记录和帮别人 review 代码的经验矩阵题的高频错误基本集中在下面几个位置我整理成了一张表常见错误出现的题型根因分析解决方案解决方案行和列的下标搞混所有矩阵题坐标轴意识不强把matrix[i][j]当成行列都对每次循环前先确认 i 是行还是 j 是行或直接改名row, col单行矩阵读取越界螺旋矩阵遍历完一行后没有及时检查边界每次收缩边界后立刻判断top bottom或left right遍历范围多算了半圈旋转图像/转置双层循环范围写成了全矩阵只遍历上半三角即j从i1开始原地修改导致原始值丢失矩阵置零用原矩阵存储标记时覆盖了信息标记区和数据区分离或者从右下角开始处理DFS 死循环被围绕的区域/岛屿数量缺少 visited 标记或标记时机不对在入栈/入队前就标记不要等到出栈才标记柱状图栈底残余未处理最大矩形循环结束没有清空单调栈数组后追加哨兵 0让所有元素自然结算4.3 面试现场的讲题节奏建议矩阵题在面试里通常不难能让考官眼前一亮的不是你写出正确答案而是你展现出的结构化拆解能力。我在面试别人和模拟面试的时候比较认可这样一套表达节奏拿到题先不要急着写代码用 30 秒到 1 分钟说清楚“我看到一个二维矩阵题敏感点是边界处理和状态标记。我的第一反应是用 XX 模型来处理最坏时间复杂度是 XX额外空间是 XX”。然后边说边写。以旋转图像为例比较好的表述是“这题我不用直接旋转坐标先转置再左右翻转两步都是二维数组的线性操作不会互相干扰。转置时只遍历上半三角避免重复交换。整体时间复杂度 O(n^2)额外空间 O(1)。”这段话一说出来考官就知道你平时做题确实总结过印象分会提高不少。还有一个我个人的小习惯面试时写矩阵题的循环边界先在草稿纸上标一遍“这个 range 的起点和终点”不要急着下笔。很多边界错误在写循环之前就能被消除值得花那十几秒。另外如果你的解法里出现了不止一个嵌套循环每层循环尽量用带语义的变量名row, col, top, bottom, left, right不要清一色用i, j。矩阵题很容易因为 i 和 j 的意义在不同代码段里发生变化而出错清晰命名能帮你自己和读你代码的人少受折磨。最后再多说一句。矩阵题刷到后面你会发现它们考察的并不是高深的数学而是“确定性问题”——确定下一步往哪走、确定哪些格子已经处理、确定状态之间如何转换。这类能力在真实开发里也非常有用因为所有二维表格、网格地图、图像像素的操作本质上都是矩阵操作。把这几道题刷扎实你练到的不仅是面试技巧还有处理复杂二维数据结构的底层功底。以后遇到再大的网格问题心里有了模型下手就不慌了。