1. 项目概述从一道经典面试题说起最近在帮团队筛选C开发岗位的候选人发现一个有趣的现象很多简历上写着“精通数据结构与算法”的朋友在面对“按对角线顺序遍历一个二维矩阵”这道题时却常常卡壳。要么是边界条件处理得磕磕绊绊要么是代码写得冗长且难以维护。这让我意识到这个看似简单的“矩阵对角线遍历”问题实际上是一个绝佳的试金石它能清晰地考察一个开发者对循环控制、索引计算、边界条件处理以及代码简洁性的综合把握能力。无论是准备技术面试的新手还是想巩固基础的资深工程师深入理解这个问题都大有裨益。简单来说给定一个M x N的矩阵不一定是方阵我们的目标不是按行或按列遍历而是沿着所有从左上到右下的对角线依次输出其中的元素。例如对于一个3x4的矩阵其对角线遍历顺序可能如下图所示数字代表输出顺序。这个问题在图像处理如某些滤波操作、科学计算访问带状矩阵等场景中都有其实际意义。今天我们就用C来彻底拆解它不仅给出解法更要讲清楚背后的思维逻辑和优化技巧。2. 核心思路拆解寻找索引变化的规律面对一个二维矩阵我们最熟悉的是逐行matrix[i][j]i外循环j内循环或逐列遍历。对角线遍历打破了这种常规顺序因此首要任务是找出新遍历顺序下行索引i和列索引j的变化规律。2.1 观察对角线特征首先我们明确“从左上到右下对角线”的定义对于矩阵中的任意元素matrix[i][j]如果它位于同一条对角线上那么这些元素的i - j值是相等的。我们可以把这个值称为“对角线标识”d i - j。对于M x N矩阵d的取值范围是从-(N-1)到M-1。然而题目要求的遍历顺序通常是按照“对角线”的起始位置来排序的。更直观的观察方法是所有对角线的起始点要么在第一行i 0要么在最后一列j N-1。并且对角线的遍历方向是交替的编号为偶数的对角线从0开始计数我们从左下向右上遍历编号为奇数的对角线我们从右上向左下遍历。2.2 确立遍历框架基于以上观察我们可以形成一个清晰的解决框架确定总循环次数总共需要遍历M N - 1条对角线。为每条对角线确定起始坐标对于前N条对角线当diag N时起始点的行索引i为0列索引j为diag。对于剩下的M - 1条对角线当diag N时起始点的行索引i为diag - N 1列索引j为N - 1。沿着当前对角线收集元素从起始点开始根据当前对角线编号的奇偶性决定移动方向i, j--或i--, j直到索引超出矩阵边界。处理遍历方向将收集到的元素根据方向决定是否反转然后存入结果。这个方法的优势在于逻辑清晰每条对角线的操作独立。但实现时需要注意索引的边界检查代码可能稍显繁琐。2.3 更简洁的“层序”模拟思路我个人更偏爱另一种思路它模拟了“逐层”访问的过程代码非常简洁。我们注意到遍历的输出顺序很像是以“左上角”为起点一层层扩散开来的过程。我们可以用两个变量row和col来追踪当前要访问的元素坐标并用一个布尔变量up来表示当前移动方向true表示向右上移动false表示向左下移动。核心算法步骤如下初始化row 0,col 0,up true。将matrix[row][col]加入结果。根据up决定下一个目标位置如果up为true向右上移动优先尝试移动到row-1, col1。如果移动后row出界row 0说明撞到了上边界此时应调整方向 (up false)。调整后如果col1未出界则下一个位置是row, col1即向右一步如果col1也出界了则下一个位置是row1, col即向下一步。如果up为false向左下移动优先尝试移动到row1, col-1。如果移动后col出界col 0说明撞到了左边界此时应调整方向 (up true)。调整后如果row1未出界则下一个位置是row1, col即向下一步如果row1也出界了则下一个位置是row, col1即向右一步。重复步骤2和3直到row M-1且col N-1将最后一个元素加入后结束。提示这种“模拟”方法的关键在于正确处理撞到矩阵边界时的转向逻辑。它把复杂的全局索引计算分解为简单的局部移动和边界判断思维负担更小代码也更易于编写和调试。3. 代码实现与逐行解析我们将采用上述第二种“模拟”方法来实现因为它最终呈现的代码非常优雅。以下是完整的C实现包含了详细的注释。#include vector #include iostream using namespace std; vectorint diagonalTraverse(vectorvectorint matrix) { // 处理空矩阵的边界情况 if (matrix.empty() || matrix[0].empty()) { return {}; } int m matrix.size(); // 行数 int n matrix[0].size(); // 列数 vectorint result; result.reserve(m * n); // 预分配空间避免动态扩容开销 int row 0, col 0; bool moveUp true; // 初始方向为右上 // 遍历所有元素总共 m*n 次循环 for (int i 0; i m * n; i) { result.push_back(matrix[row][col]); if (moveUp) { // 尝试向右上方移动 if (row - 1 0 col 1 n) { // 右上位置合法直接移动 --row; col; } else { // 撞到上边界或右边界需要转向 moveUp false; // 优先尝试向右移动如果可能 if (col 1 n) { col; } else { // 如果无法向右即在最后一列则向下移动 row; } } } else { // 尝试向左下方移动 if (row 1 m col - 1 0) { // 左下位置合法直接移动 row; --col; } else { // 撞到下边界或左边界需要转向 moveUp true; // 优先尝试向下移动如果可能 if (row 1 m) { row; } else { // 如果无法向下即在最后一行则向右移动 col; } } } } return result; } // 辅助函数打印结果 void printVector(const vectorint vec) { cout [; for (size_t i 0; i vec.size(); i) { cout vec[i]; if (i ! vec.size() - 1) cout , ; } cout ] endl; } int main() { // 测试用例1: 3x4矩阵 vectorvectorint mat1 { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} }; vectorint res1 diagonalTraverse(mat1); cout 3x4矩阵遍历结果: ; printVector(res1); // 预期: [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12] // 测试用例2: 2x2矩阵 vectorvectorint mat2 { {1, 2}, {3, 4} }; vectorint res2 diagonalTraverse(mat2); cout 2x2矩阵遍历结果: ; printVector(res2); // 预期: [1, 2, 3, 4] // 测试用例3: 1x5行向量 vectorvectorint mat3 {{1, 2, 3, 4, 5}}; vectorint res3 diagonalTraverse(mat3); cout 1x5矩阵遍历结果: ; printVector(res3); // 预期: [1, 2, 3, 4, 5] // 测试用例4: 4x1列向量 vectorvectorint mat4 {{1}, {2}, {3}, {4}}; vectorint res4 diagonalTraverse(mat4); cout 4x1矩阵遍历结果: ; printVector(res4); // 预期: [1, 2, 3, 4] return 0; }3.1 关键代码段解析让我们聚焦于核心的diagonalTraverse函数中的方向处理逻辑这是最容易出错的地方。向右上移动时的边界处理 (if (moveUp)分支):if (row - 1 0 col 1 n) { // 情况A右上角位置在矩阵内正常移动 --row; col; } else { // 情况B撞到边界上边界row-10 或 右边界col1n moveUp false; // 必须转向 if (col 1 n) { // 情况B1虽然撞了上边界但右边还有空间则向右移动一步 col; } else { // 情况B2既撞了上边界又处于最后一列则只能向下移动一步 // 这种情况发生在矩阵的右上角顶点 row; } }这里的逻辑优先级是先尝试正常斜向移动失败后转向转向后优先尝试水平向右移动不行再垂直向下移动。这个优先级保证了遍历路径的连续性符合题目要求的顺序。向左下移动时的边界处理 (else分支):逻辑与右上分支对称但优先移动的方向不同。撞边界后优先尝试垂直向下移动不行再水平向右移动。3.2 复杂度分析时间复杂度O(M * N)。我们恰好访问了矩阵中的每一个元素一次因此时间复杂度与矩阵的元素总数呈线性关系。空间复杂度O(1)。如果不考虑存储结果的vector我们只使用了几个整型和布尔变量是常数空间。结果存储本身是任务要求通常不计入空间复杂度分析但明确来说输出空间是O(M * N)。4. 边界条件与常见陷阱在实际编码和面试中以下几个边界情况和陷阱需要特别注意4.1 空矩阵输入这是最基础的防御性编程。如果输入矩阵的行数M或列数N为0函数应立即返回一个空数组。我们的代码在开头通过matrix.empty() || matrix[0].empty()进行了检查。4.2 单行或单列矩阵当矩阵只有一行 (M 1) 或只有一列 (N 1) 时对角线遍历就退化成了普通的行遍历或列遍历。我们的算法能否正确处理单行矩阵初始moveUp true。第一次尝试右上移动会失败row-1 0转向后进入if (col 1 n)分支向右移动。后续所有步骤都会因为无法斜向移动而不断向右直到结束。结果正确。单列矩阵逻辑类似会不断向下移动。测试用例3和4已验证了这一点。4.3 转向逻辑的优先级这是本解法的核心难点也是面试官喜欢追问的地方。为什么撞上边界后有时向右走有时向下走规则如下表所示当前方向撞到的边界转向后优先动作触发条件示例位置右上(Up)上边界 (row 0)向右 (col)不在最后一列时如3x4矩阵的(0,1)点之后右上(Up)右边界 (col N-1)向下 (row)撞到右上角时如3x4矩阵的(0,3)点之后左下(Down)左边界 (col 0)向下 (row)不在最后一行时如3x4矩阵的(1,0)点之后左下(Down)下边界 (row M-1)向右 (col)撞到左下角时如3x4矩阵的(2,0)点之后记忆技巧你可以想象一个“贪吃蛇”在矩阵里沿对角线爬行撞墙后就沿着墙边拐弯。拐弯时它总是优先尝试“顺着原方向的前进侧”的墙边移动。对于“右上”方向它的前进侧是右侧和上侧撞墙后优先向右对于“左下”方向前进侧是下侧和左侧撞墙后优先向下。4.4 索引越界检查的顺序在条件判断if (row - 1 0 col 1 n)中两个条件的顺序在C/C中很重要。由于逻辑与的短路求值特性将可能快速失败的检查放在前面是良好的实践。这里row-1 0和col1 n的失败概率取决于当前遍历位置没有绝对优劣。但务必确保检查的是“下一个”目标位置而不是当前位置。5. 算法变体与扩展思考掌握了基础解法后我们可以思考一些变体和扩展问题这有助于深化理解。5.1 从其他角开始或按相反方向遍历从右下角开始向左上角遍历只需将初始坐标设为(M-1, N-1)并将所有移动方向取反变----变边界判断逻辑做相应调整即可。按“从右下到左上”的顺序遍历每条对角线这改变了对角线的访问顺序但每条对角线内部的遍历方向规则可能不变。这需要重新定义“起始点”的顺序。5.2 仅遍历特定区域的对角线有时我们只关心矩阵中心附近、或者主对角线及其两侧若干条对角线上的元素例如在解三对角方程组时。此时我们可以修改循环的起始和结束条件只生成目标对角线的标识d然后根据d计算出该对角线上所有有效元素的(i, j)坐标进行访问。这种方法即2.2节提到的第一种思路在针对性访问时更高效。5.3 与“之字形打印矩阵”的关系“对角线遍历”和经典的“之字形打印矩阵”问题非常相似但后者通常特指“行”的之字形访问第一行从左到右第二行从右到左以此类推。而对角线遍历是“对角线”的之字形访问。两者的核心思想是相通的在直线遍历中加入方向交替的逻辑。理解其中一个对解决另一个大有帮助。5.4 在更高维度或特殊矩阵上的应用虽然题目是二维矩阵但思考可以延伸。对于三维数组是否存在“体对角线”遍历对于稀疏矩阵按对角线遍历可能有助于聚集非零元素。对于分块矩阵对角线遍历可以引导块间的计算顺序。这些扩展思考体现了将具体算法抽象为通用模式的能力。6. 调试技巧与测试用例设计写出代码只是第一步确保其正确性更为关键。以下是一些实用的调试和测试方法。6.1 设计全面的测试用例一个健壮的测试集应包含以下类型常规矩形3x4,4x3验证非方阵情况。方阵1x1,2x2,3x3特别是1x1是重要边界。退化矩阵1xN(行向量)Mx1(列向量)0x0(空矩阵)0x5,5x0。极值数据矩阵元素值较大或较小测试是否只是机械移动而没用到值。手动推算小案例对于2x2或3x3矩阵手工写出遍历顺序与程序输出对比这是最快速的验证。6.2 可视化调试对于二维问题最好的调试方式就是“画出来”。你可以写一个简单的辅助函数在控制台打印出矩阵并标记出每一步访问的位置。void printMatrixWithCursor(const vectorvectorint mat, int curRow, int curCol) { for(int i0; imat.size(); i){ for(int j0; jmat[i].size(); j){ if(icurRow jcurCol) cout [ mat[i][j] ] ; else cout mat[i][j] ; } cout endl; } cout ------------------- endl; }在遍历循环中调用此函数可以清晰看到“贪吃蛇”的移动路径直观定位转向逻辑的错误。6.3 核心逻辑单元测试将复杂的转向逻辑抽离成一个独立的函数getNextPosition(int row, int col, bool moveUp, int m, int n)专门计算下一个坐标和方向。然后针对这个函数编写测试用例验证在各种边界位置如四个角、四条边的转向是否正确。这比测试整个遍历函数更容易定位问题。7. 性能优化与工程化考量在算法正确的基础上我们还可以从工程和性能角度做一些优化。7.1 预分配结果容器空间如代码所示在创建结果vectorint result后立即使用result.reserve(m * n)预分配足够容纳所有元素的内存。这避免了在push_back过程中可能发生的多次动态内存分配和复制对于大矩阵能带来显著的性能提升。这是一个良好的C习惯。7.2 避免不必要的分支判断在内层循环中if (moveUp) ... else ...是一个分支。对于超大规模矩阵分支预测失败可能会带来轻微开销。有一种优化思路是放弃布尔变量改为使用一个整数direction(1代表右上-1代表左下)这样在计算下一个坐标时可以用row direction, col - direction来表示斜向移动但边界判断和转向逻辑会变得复杂代码可读性下降。在绝大多数情况下清晰可读的代码比这点微优化更重要。除非在性能敏感的底层库中否则不建议使用。7.3 使用迭代器或指针高级对于追求极致性能的场景如果矩阵数据在内存中是连续存储的如C风格二维数组或vectorvectorint且内层向量长度固定我们可以通过计算内存偏移量来直接访问元素减少二维索引的开销。但这会严重牺牲代码的可读性和通用性仅在对性能有极端要求时考虑。7.4 代码可读性与维护性当前的实现将方向判断和移动逻辑清晰地放在了一起。另一种可读性更高的写法是将“获取下一个坐标”的功能封装成一个函数主循环只负责调用和收集结果。这样主循环的逻辑会非常干净while (result.size() total) { result.push_back(matrix[row][col]); tie(row, col, moveUp) getNext(row, col, moveUp, m, n); // C17结构化绑定 }哪种风格更好取决于团队规范和项目复杂度。在面试中清晰完整地实现核心逻辑是第一位的。8. 在面试中如何应对如果你在面试中被问到这个问题以下步骤可以帮助你清晰、自信地解答澄清问题首先确认矩阵是否是方阵遍历的起始点通常是左上角[0,0]以及对角线遍历的具体顺序通常是指定交替方向。可以画一个3x4的例子让面试官确认。阐述思路先描述你观察到的规律对角线标识、起始点特征、方向交替。然后提出你的解决方案优先推荐“模拟移动”法因为它思路直观易于编码且边界条件处理相对集中。边写边讲在写代码时同步解释你的思考过程。特别是写到边界判断和转向逻辑时要说明为什么这么处理例如“现在在右上移动如果撞到上边界我需要转向。转向后优先尝试向右走因为...如果右边没路了那一定是在最后一列这时只能向下”。手动测试写完代码后不要等面试官说主动用一个简单例子如2x3矩阵走一遍你的代码验证逻辑。分析复杂度主动给出时间复杂度和空间复杂度分析。讨论边界提及空矩阵、单行/单列矩阵等特殊情况并说明你的代码如何处理。思考扩展如果时间允许可以简要提一下其他解法如按对角线标识分组或变体问题展示你的思维广度。一个常见的面试陷阱面试官可能会问“如果矩阵非常大无法一次性装入内存怎么办” 这其实是在考察你对外部排序或流式处理的理解。你可以回答如果按对角线遍历同一对角线上的元素在内存中的位置可能不连续无法高效进行分块IO。此时更可行的方案可能是按行或按列分块处理或者如果问题允许考虑其他更适合外部存储的访问模式。这体现了你从实际问题到工程约束的思考深度。对角线遍历问题就像一把精巧的钥匙它打开的不仅是一个具体的算法解法更是对循环、索引、边界和状态转换这些编程基础元素的深刻理解。下次当你看到二维数组时不妨在脑海里多画几条对角线这种多维度的思考训练对于解决更复杂的图像、网格类问题将大有帮助。
