1. 矩阵问题在算法面试中的核心地位最近在整理LeetCode Hot100的刷题笔记时发现矩阵类问题出现的频率相当高。这类问题往往看似简单但要在面试中快速写出bug-free的代码并不容易。今天我们就来系统梳理矩阵类题目的解题套路掌握这些技巧后面对旋转、搜索、路径等问题都能游刃有余。矩阵问题之所以成为面试常客是因为它能全面考察候选人的以下能力对二维数据结构的操作熟练度边界条件的处理能力空间复杂度的优化意识递归与迭代的转换技巧2. 矩阵遍历的四种经典模式2.1 螺旋遍历Spiral Order这是最常见的矩阵遍历方式LeetCode第54题就是典型代表。关键在于维护四个边界top、bottom、left、right然后按照右→下→左→上的顺序循环。def spiralOrder(matrix): if not matrix: return [] res [] top, bottom 0, len(matrix)-1 left, right 0, len(matrix[0])-1 while True: # 从左到右 for i in range(left, right1): res.append(matrix[top][i]) top 1 if top bottom: break # 从上到下 for i in range(top, bottom1): res.append(matrix[i][right]) right - 1 if left right: break # 从右到左 for i in range(right, left-1, -1): res.append(matrix[bottom][i]) bottom - 1 if top bottom: break # 从下到上 for i in range(bottom, top-1, -1): res.append(matrix[i][left]) left 1 if left right: break return res注意边界变化后要立即检查是否越界这是最容易出错的地方。我在面试中见过不少候选人忘记检查导致死循环。2.2 对角线遍历LeetCode第498题要求按对角线顺序遍历矩阵。观察发现奇数对角线方向向上行减列加偶数对角线方向向下行加列减def findDiagonalOrder(matrix): if not matrix: return [] m, n len(matrix), len(matrix[0]) res [] row col 0 for _ in range(m * n): res.append(matrix[row][col]) if (row col) % 2 0: # 向上遍历 if col n - 1: row 1 elif row 0: col 1 else: row - 1 col 1 else: # 向下遍历 if row m - 1: col 1 elif col 0: row 1 else: row 1 col - 1 return res2.3 旋转遍历Rotate ImageLeetCode第48题要求原地旋转图像。这类问题的关键是找到旋转前后坐标的映射关系顺时针90度matrix[i][j] → matrix[j][n-1-i]逆时针90度matrix[i][j] → matrix[n-1-j][i]def rotate(matrix): n len(matrix) # 先转置 for i in range(n): for j in range(i, n): matrix[i][j], matrix[j][i] matrix[j][i], matrix[i][j] # 再水平翻转 for i in range(n): matrix[i] matrix[i][::-1]2.4 之字形遍历Zigzag这种遍历方式在构建某些特殊矩阵时会用到核心是控制方向变量def zigzag(matrix): if not matrix: return [] m, n len(matrix), len(matrix[0]) res [] for i in range(m): if i % 2 0: res matrix[i] else: res matrix[i][::-1] return res3. 矩阵搜索问题精解3.1 二分搜索变种LeetCode第74题搜索二维矩阵和第240题搜索二维矩阵II是经典变种第74题可以看作展开的一维数组进行二分第240题需要利用行列有序的特性从右上角开始搜索# 第240题解法 def searchMatrix(matrix, target): if not matrix: return False row, col 0, len(matrix[0])-1 while row len(matrix) and col 0: if matrix[row][col] target: return True elif matrix[row][col] target: row 1 else: col - 1 return False3.2 岛屿问题系列岛屿类问题(如200题)通常使用DFS/BFS遍历def numIslands(grid): if not grid: return 0 count 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] 1: self.dfs(grid, i, j) count 1 return count def dfs(grid, i, j): if i0 or j0 or ilen(grid) or jlen(grid[0]) or grid[i][j] ! 1: return grid[i][j] 0 # 标记为已访问 self.dfs(grid, i1, j) self.dfs(grid, i-1, j) self.dfs(grid, i, j1) self.dfs(grid, i, j-1)实际面试中面试官可能会要求比较DFS和BFS的实现差异。DFS代码更简洁但BFS更适合大规模数据。4. 动态规划在矩阵中的应用4.1 最小路径和LeetCode 64def minPathSum(grid): if not grid: return 0 m, n len(grid), len(grid[0]) dp [[0]*n for _ in range(m)] dp[0][0] grid[0][0] # 初始化第一列 for i in range(1, m): dp[i][0] dp[i-1][0] grid[i][0] # 初始化第一行 for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j] for i in range(1, m): for j in range(1, n): dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j] return dp[-1][-1]4.2 最大正方形LeetCode 221def maximalSquare(matrix): if not matrix: return 0 m, n len(matrix), len(matrix[0]) dp [[0]*(n1) for _ in range(m1)] max_len 0 for i in range(1, m1): for j in range(1, n1): if matrix[i-1][j-1] 1: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1 max_len max(max_len, dp[i][j]) return max_len * max_len5. 矩阵问题优化技巧5.1 空间复杂度优化很多矩阵DP问题可以将空间复杂度从O(mn)优化到O(n)def minPathSum(grid): if not grid: return 0 m, n len(grid), len(grid[0]) dp [0]*n dp[0] grid[0][0] for j in range(1, n): dp[j] dp[j-1] grid[0][j] for i in range(1, m): dp[0] grid[i][0] for j in range(1, n): dp[j] min(dp[j], dp[j-1]) grid[i][j] return dp[-1]5.2 方向数组的使用在处理相邻单元格时使用方向数组能让代码更简洁# 上下左右四个方向 directions [(-1,0),(1,0),(0,-1),(0,1)] for di, dj in directions: ni, nj i di, j dj if 0 ni m and 0 nj n: # 处理相邻单元格6. 常见错误与调试技巧索引越界矩阵问题最容易出现数组越界。建议先检查空矩阵情况在访问matrix[i][j]前确认i,j的范围使用辅助函数处理边界检查方向混淆旋转、遍历方向容易搞混。建议画图辅助理解用3x3矩阵手动模拟添加详细的注释说明方向原地修改问题有些题目要求原地修改矩阵这时要注意修改顺序是否会影响后续判断是否需要额外的标记方式能否使用位运算同时存储新旧状态复杂度过高矩阵问题容易写出O(mn)空间复杂度的解法。优化思路观察状态转移是否只需要前一行/列考虑用位图代替二维数组尝试从不同角度进行状态压缩7. 高频面试题分类训练7.1 基础操作类旋转图像48矩阵置零73螺旋矩阵54对角线遍历4987.2 搜索类搜索二维矩阵74搜索二维矩阵II240单词搜索79岛屿数量2007.3 动态规划类最小路径和64最大正方形221不同路径62地下城游戏1747.4 其他变种矩阵中的最长递增路径32901矩阵542矩阵区域和1314稀疏矩阵乘法3118. 实战建议模板化训练将每种题型总结成固定解题模板如螺旋遍历 → 四边界法岛屿问题 → DFS/BFS模板矩阵DP → 初始化首行首列维度转换思维有时将矩阵视为图节点单元格边相邻关系能获得新思路复杂度分析明确告知面试官你的解法时间/空间复杂度并讨论优化可能测试用例设计考虑以下特殊情况空矩阵1x1矩阵单行/单列矩阵全0/全1矩阵可视化调试对于复杂逻辑可以在纸上画出矩阵和指针移动轨迹辅助理解最后分享一个我在面试中总结的小技巧当遇到复杂矩阵问题时先和面试官确认输入矩阵的特性是否有序是否有特殊结构这往往能发现题目隐藏的简化条件。