1. 矩阵遍历在算法面试中的核心地位作为算法面试中最基础也最高频的考察点之一矩阵遍历能力直接决定了候选人能否顺利解决二维数组相关的各类变种题目。我在面试候选人时发现超过60%的数组类题目最终都会转化为某种形式的矩阵遍历问题。比如经典的岛屿数量问题Leetcode 200表面上是考察DFS/BFS本质上就是矩阵遍历技巧的灵活运用。矩阵之所以成为算法题中的常客是因为它完美模拟了现实中的棋盘、地图、图像等二维结构。不同于线性数组的单向遍历矩阵操作需要同时考虑行和列两个维度的移动逻辑这给边界条件处理和遍历顺序设计带来了独特挑战。以2023年Leetcode周赛第430场的第四题为例参赛者需要在对角线遍历矩阵的基础上进行动态规划没有扎实的矩阵遍历基本功根本无法下手。2. 矩阵遍历的四种基础范式2.1 顺序遍历最朴素的暴力解法最基本的矩阵遍历方式就是双重循环嵌套def traverse(matrix): for i in range(len(matrix)): # 行遍历 for j in range(len(matrix[0])): # 列遍历 print(matrix[i][j])这种遍历方式虽然简单但在处理某些特定问题时效率低下。比如在搜索排序矩阵Leetcode 240时顺序遍历的O(mn)时间复杂度远不如从右上角开始的Z字形搜索高效。2.2 螺旋遍历边界收缩的艺术螺旋遍历是面试中的高频考点其核心在于通过四重循环模拟顺时针旋转def spiralOrder(matrix): res [] while matrix: res matrix.pop(0) # 上边界 if matrix and matrix[0]: for row in matrix: res.append(row.pop()) # 右边界 if matrix: res matrix.pop()[::-1] # 下边界 if matrix and matrix[0]: for row in matrix[::-1]: res.append(row.pop(0)) # 左边界 return res实际编码时特别要注意矩阵剩余单行或单列时的特殊情况处理。我在最初实现时曾因忽略matrix[0]的空判断导致多次提交失败。2.3 对角线遍历索引计算的陷阱对角线遍历Leetcode 498需要处理索引和的奇偶性def findDiagonalOrder(mat): if not mat: return [] m, n len(mat), len(mat[0]) res [] for s in range(m n - 1): if s % 2 0: # 向上遍历 i min(s, m-1) j s - i while i 0 and j n: res.append(mat[i][j]) i - 1 j 1 else: # 向下遍历 j min(s, n-1) i s - j while j 0 and i m: res.append(mat[i][j]) i 1 j - 1 return res这里最容易出错的是边界条件s m n - 2时的索引计算。建议在纸上画出3×4和4×3矩阵的遍历路径进行验证。2.4 旋转遍历维度变换的思维训练矩阵旋转Leetcode 48考察的是对维度转换的理解def rotate(matrix): n len(matrix) # 先转置 for i in range(n): for j in range(i, n): matrix[j][i], matrix[i][j] matrix[i][j], matrix[j][i] # 再水平翻转 for i in range(n): for j in range(n//2): matrix[i][j], matrix[i][-j-1] matrix[i][-j-1], matrix[i][j]注意这里的内层循环从i开始避免重复交换以及水平翻转时j的范围是n//2。这类题目建议始终用奇数边和偶数边矩阵各测试一次。3. 矩阵遍历的优化技巧3.1 方向数组的妙用在DFS/BFS类问题中使用方向数组可以大幅简化代码directions [(-1,0),(1,0),(0,-1),(0,1)] # 上下左右 def dfs(matrix, i, j, visited): if (i,j) in visited or not (0ilen(matrix) and 0jlen(matrix[0])): return visited.add((i,j)) for di, dj in directions: dfs(matrix, idi, jdj, visited)这种方式比写四个独立的递归调用更不易出错也便于扩展到八连通的情况。在解决单词搜索Leetcode 79时这种写法优势尤为明显。3.2 虚拟边界的处理技巧当需要处理矩阵边缘元素时可以尝试添加虚拟边界来统一逻辑# 在原始矩阵外围添加一圈特殊值 padded [[-1]*(n2)] [[-1]row[-1] for row in matrix] [[-1]*(n2)]这种方法在解决生命游戏Leetcode 289时能避免大量的边界条件判断。不过要注意内存开销对于超大矩阵可能不适用。3.3 原地修改的空间优化当题目允许修改输入矩阵时可以利用矩阵本身存储状态信息。比如用0表示陆地1表示水域-1表示已访问的陆地用第一行和第一列记录该行/列是否需要置零Leetcode 73这种技巧可以将空间复杂度从O(mn)降到O(1)但会显著增加代码的复杂度。建议先用额外空间写出正确解再考虑优化。4. 矩阵遍历的实战应用4.1 动态规划中的矩阵遍历许多二维DP问题本质上都是特殊的矩阵遍历。以最小路径和Leetcode 64为例def minPathSum(grid): m, n len(grid), len(grid[0]) for i in range(1, m): grid[i][0] grid[i-1][0] for j in range(1, n): grid[0][j] grid[0][j-1] for i in range(1, m): for j in range(1, n): grid[i][j] min(grid[i-1][j], grid[i][j-1]) return grid[-1][-1]这里先处理第一行和第一列的边界情况再按顺序遍历内部元素。类似的思想也适用于不同路径Leetcode 62等题目。4.2 图论问题中的矩阵建模矩阵可以很好地表示图的邻接关系。比如腐烂的橘子Leetcode 994def orangesRotting(grid): m, n len(grid), len(grid[0]) queue [] fresh 0 for i in range(m): for j in range(n): if grid[i][j] 2: queue.append((i,j)) elif grid[i][j] 1: fresh 1 # BFS遍历...这种问题需要同时维护队列和未腐烂计数是多层遍历的典型应用。4.3 位运算与矩阵的奇妙组合某些特殊场景下可以用位运算优化矩阵操作。比如# 判断数独有效性Leetcode 36 rows [0] * 9 cols [0] * 9 boxes [0] * 9 for i in range(9): for j in range(9): num board[i][j] if num .: continue mask 1 (int(num) - 1) if rows[i] mask or cols[j] mask or boxes[(i//3)*3j//3] mask: return False rows[i] | mask cols[j] | mask boxes[(i//3)*3j//3] | mask这种解法将每行/列/宫格的数字出现情况压缩到一个整数中比用哈希表更高效。5. 高频错误与调试技巧5.1 索引越界的常见场景矩阵遍历中最容易犯的错误就是索引越界特别是在处理螺旋遍历的最后几圈对角线遍历的转折点DFS递归的终止条件建议在访问matrix[i][j]前总是先检查if 0 i len(matrix) and 0 j len(matrix[0]): # 安全访问5.2 方向变量的同步更新当需要同时维护行和列两个索引时容易犯不同步的错误# 错误示例i和j没有同步更新 while condition: j (j 1) % n i j // n # 这行经常被遗忘正确的做法是预先计算下一个位置next_i, next_j i di, j dj if 0 next_i m and 0 next_j n: i, j next_i, next_j5.3 复杂遍历的调试方法对于螺旋、对角线等复杂遍历建议先在纸上画出小矩阵如3×4的遍历路径在循环内打印当前位置(i,j)和对应元素值使用assert检查每次移动后的位置是否合法对偶数/奇数尺寸矩阵分别测试例如调试对角线遍历时可以print(fStep {s}: i{i}, j{j}, val{mat[i][j]}) assert 0 i m and 0 j n6. 矩阵遍历的进阶训练6.1 推荐练习题目按照难度梯度建议的刷题顺序重塑矩阵Leetcode 566 - 基础索引转换托普利茨矩阵Leetcode 766 - 对角线特征检查二维区域和检索Leetcode 304 - 前缀和思想矩阵置零Leetcode 73 - 空间优化技巧搜索二维矩阵IILeetcode 240 - 特殊遍历策略孤独像素ILeetcode 531 - 行列特征统计最大加号标志Leetcode 764 - 多方向遍历对角线遍历IILeetcode 1424 - 进阶索引计算6.2 竞赛级优化技巧在周赛和笔试中可以尝试这些优化使用zip(*matrix)快速转置矩阵用itertools.product简化双重循环from itertools import product for i, j in product(range(m), range(n)): # 代替嵌套循环对于二进制矩阵可以用整数的位表示行/列预先计算行列的前缀和以减少重复计算6.3 可视化调试工具推荐使用Python的matplotlib辅助调试import matplotlib.pyplot as plt def plot_matrix(matrix): plt.imshow(matrix) for i in range(len(matrix)): for j in range(len(matrix[0])): plt.text(j, i, str(matrix[i][j]), hacenter, vacenter) plt.show()这对于观察遍历顺序、验证旋转结果等场景特别有用。 
长河君 · 2026/8/18 21:04:07 · 阅读 1.2k 矩阵遍历算法：面试必备的四种范式与优化技巧
1. 矩阵遍历在算法面试中的核心地位作为算法面试中最基础也最高频的考察点之一矩阵遍历能力直接决定了候选人能否顺利解决二维数组相关的各类变种题目。我在面试候选人时发现超过60%的数组类题目最终都会转化为某种形式的矩阵遍历问题。比如经典的岛屿数量问题Leetcode 200表面上是考察DFS/BFS本质上就是矩阵遍历技巧的灵活运用。矩阵之所以成为算法题中的常客是因为它完美模拟了现实中的棋盘、地图、图像等二维结构。不同于线性数组的单向遍历矩阵操作需要同时考虑行和列两个维度的移动逻辑这给边界条件处理和遍历顺序设计带来了独特挑战。以2023年Leetcode周赛第430场的第四题为例参赛者需要在对角线遍历矩阵的基础上进行动态规划没有扎实的矩阵遍历基本功根本无法下手。2. 矩阵遍历的四种基础范式2.1 顺序遍历最朴素的暴力解法最基本的矩阵遍历方式就是双重循环嵌套def traverse(matrix): for i in range(len(matrix)): # 行遍历 for j in range(len(matrix[0])): # 列遍历 print(matrix[i][j])这种遍历方式虽然简单但在处理某些特定问题时效率低下。比如在搜索排序矩阵Leetcode 240时顺序遍历的O(mn)时间复杂度远不如从右上角开始的Z字形搜索高效。2.2 螺旋遍历边界收缩的艺术螺旋遍历是面试中的高频考点其核心在于通过四重循环模拟顺时针旋转def spiralOrder(matrix): res [] while matrix: res matrix.pop(0) # 上边界 if matrix and matrix[0]: for row in matrix: res.append(row.pop()) # 右边界 if matrix: res matrix.pop()[::-1] # 下边界 if matrix and matrix[0]: for row in matrix[::-1]: res.append(row.pop(0)) # 左边界 return res实际编码时特别要注意矩阵剩余单行或单列时的特殊情况处理。我在最初实现时曾因忽略matrix[0]的空判断导致多次提交失败。2.3 对角线遍历索引计算的陷阱对角线遍历Leetcode 498需要处理索引和的奇偶性def findDiagonalOrder(mat): if not mat: return [] m, n len(mat), len(mat[0]) res [] for s in range(m n - 1): if s % 2 0: # 向上遍历 i min(s, m-1) j s - i while i 0 and j n: res.append(mat[i][j]) i - 1 j 1 else: # 向下遍历 j min(s, n-1) i s - j while j 0 and i m: res.append(mat[i][j]) i 1 j - 1 return res这里最容易出错的是边界条件s m n - 2时的索引计算。建议在纸上画出3×4和4×3矩阵的遍历路径进行验证。2.4 旋转遍历维度变换的思维训练矩阵旋转Leetcode 48考察的是对维度转换的理解def rotate(matrix): n len(matrix) # 先转置 for i in range(n): for j in range(i, n): matrix[j][i], matrix[i][j] matrix[i][j], matrix[j][i] # 再水平翻转 for i in range(n): for j in range(n//2): matrix[i][j], matrix[i][-j-1] matrix[i][-j-1], matrix[i][j]注意这里的内层循环从i开始避免重复交换以及水平翻转时j的范围是n//2。这类题目建议始终用奇数边和偶数边矩阵各测试一次。3. 矩阵遍历的优化技巧3.1 方向数组的妙用在DFS/BFS类问题中使用方向数组可以大幅简化代码directions [(-1,0),(1,0),(0,-1),(0,1)] # 上下左右 def dfs(matrix, i, j, visited): if (i,j) in visited or not (0ilen(matrix) and 0jlen(matrix[0])): return visited.add((i,j)) for di, dj in directions: dfs(matrix, idi, jdj, visited)这种方式比写四个独立的递归调用更不易出错也便于扩展到八连通的情况。在解决单词搜索Leetcode 79时这种写法优势尤为明显。3.2 虚拟边界的处理技巧当需要处理矩阵边缘元素时可以尝试添加虚拟边界来统一逻辑# 在原始矩阵外围添加一圈特殊值 padded [[-1]*(n2)] [[-1]row[-1] for row in matrix] [[-1]*(n2)]这种方法在解决生命游戏Leetcode 289时能避免大量的边界条件判断。不过要注意内存开销对于超大矩阵可能不适用。3.3 原地修改的空间优化当题目允许修改输入矩阵时可以利用矩阵本身存储状态信息。比如用0表示陆地1表示水域-1表示已访问的陆地用第一行和第一列记录该行/列是否需要置零Leetcode 73这种技巧可以将空间复杂度从O(mn)降到O(1)但会显著增加代码的复杂度。建议先用额外空间写出正确解再考虑优化。4. 矩阵遍历的实战应用4.1 动态规划中的矩阵遍历许多二维DP问题本质上都是特殊的矩阵遍历。以最小路径和Leetcode 64为例def minPathSum(grid): m, n len(grid), len(grid[0]) for i in range(1, m): grid[i][0] grid[i-1][0] for j in range(1, n): grid[0][j] grid[0][j-1] for i in range(1, m): for j in range(1, n): grid[i][j] min(grid[i-1][j], grid[i][j-1]) return grid[-1][-1]这里先处理第一行和第一列的边界情况再按顺序遍历内部元素。类似的思想也适用于不同路径Leetcode 62等题目。4.2 图论问题中的矩阵建模矩阵可以很好地表示图的邻接关系。比如腐烂的橘子Leetcode 994def orangesRotting(grid): m, n len(grid), len(grid[0]) queue [] fresh 0 for i in range(m): for j in range(n): if grid[i][j] 2: queue.append((i,j)) elif grid[i][j] 1: fresh 1 # BFS遍历...这种问题需要同时维护队列和未腐烂计数是多层遍历的典型应用。4.3 位运算与矩阵的奇妙组合某些特殊场景下可以用位运算优化矩阵操作。比如# 判断数独有效性Leetcode 36 rows [0] * 9 cols [0] * 9 boxes [0] * 9 for i in range(9): for j in range(9): num board[i][j] if num .: continue mask 1 (int(num) - 1) if rows[i] mask or cols[j] mask or boxes[(i//3)*3j//3] mask: return False rows[i] | mask cols[j] | mask boxes[(i//3)*3j//3] | mask这种解法将每行/列/宫格的数字出现情况压缩到一个整数中比用哈希表更高效。5. 高频错误与调试技巧5.1 索引越界的常见场景矩阵遍历中最容易犯的错误就是索引越界特别是在处理螺旋遍历的最后几圈对角线遍历的转折点DFS递归的终止条件建议在访问matrix[i][j]前总是先检查if 0 i len(matrix) and 0 j len(matrix[0]): # 安全访问5.2 方向变量的同步更新当需要同时维护行和列两个索引时容易犯不同步的错误# 错误示例i和j没有同步更新 while condition: j (j 1) % n i j // n # 这行经常被遗忘正确的做法是预先计算下一个位置next_i, next_j i di, j dj if 0 next_i m and 0 next_j n: i, j next_i, next_j5.3 复杂遍历的调试方法对于螺旋、对角线等复杂遍历建议先在纸上画出小矩阵如3×4的遍历路径在循环内打印当前位置(i,j)和对应元素值使用assert检查每次移动后的位置是否合法对偶数/奇数尺寸矩阵分别测试例如调试对角线遍历时可以print(fStep {s}: i{i}, j{j}, val{mat[i][j]}) assert 0 i m and 0 j n6. 矩阵遍历的进阶训练6.1 推荐练习题目按照难度梯度建议的刷题顺序重塑矩阵Leetcode 566 - 基础索引转换托普利茨矩阵Leetcode 766 - 对角线特征检查二维区域和检索Leetcode 304 - 前缀和思想矩阵置零Leetcode 73 - 空间优化技巧搜索二维矩阵IILeetcode 240 - 特殊遍历策略孤独像素ILeetcode 531 - 行列特征统计最大加号标志Leetcode 764 - 多方向遍历对角线遍历IILeetcode 1424 - 进阶索引计算6.2 竞赛级优化技巧在周赛和笔试中可以尝试这些优化使用zip(*matrix)快速转置矩阵用itertools.product简化双重循环from itertools import product for i, j in product(range(m), range(n)): # 代替嵌套循环对于二进制矩阵可以用整数的位表示行/列预先计算行列的前缀和以减少重复计算6.3 可视化调试工具推荐使用Python的matplotlib辅助调试import matplotlib.pyplot as plt def plot_matrix(matrix): plt.imshow(matrix) for i in range(len(matrix)): for j in range(len(matrix[0])): plt.text(j, i, str(matrix[i][j]), hacenter, vacenter) plt.show()这对于观察遍历顺序、验证旋转结果等场景特别有用。