LeetCode 498中等矩阵模拟
对角线遍历 图解题解
这道题到底在问什么
给定一个 m×n 的矩阵 mat，按对角线的顺序返回矩阵中的所有元素（组成一个一维数组）。注意方向：第一条对角线从下往上读，下一条从上往下读，如此上下交替。
- 输入
- mat = [[1,2,3],[4,5,6],[7,8,9]]
- 输出
- [1,2,4,7,5,3,6,8,9]
- 解释
- 先 1；再 2、4；再 7、5、3；再 6、8；最后 9。
最优解：一步一步想明白
- 33×3 矩阵这是我们的例子：一个 3×3 的矩阵。我们要把这 9 个数字，按对角线的规律排成一条线读出来。
- 4同一条斜线 = 行号+列号相同关键观察：左下到右上的这种斜线，上面每个格子的「行号 + 列号」是同一个数。我们把这个和叫做 d，d 从 0 一直数到最大，就是一条条对角线。
- 5i+j=0 只有一个格子第 0 条对角线 d=0：只有 (0,0) 一个格子，里面是 1（紫色高亮）。这是最左上角那条最短的斜线。
- 6i+j=1 有两个格子第 1 条对角线 d=1：(0,1)、(1,0) 两格，值是 2 和 4。它们的行号+列号都等于 1，所以是同一条斜线。
- 7i+j=2 有三个格子第 2 条对角线 d=2：(0,2)、(1,1)、(2,0) 三格，值是 3、5、7。这是最中间、最长的一条斜线。
- 8剩下两条短斜线最后两条：d=3 是 (1,2)、(2,1)，值 6、8（紫色）；d=4 是 (2,2)，值 9（蓝色）。整张图被切成了 5 条对角线。
- 9d=0..4 整张图切成 5 条斜线把 5 条对角线一起标出来：d=0 到 d=4，一共 m+n-1 = 5 条。我们要按 d 从小到大、一条一条读完。接下来定方向。
- 10偶数条向上、奇数条向下光按对角线还不够，方向要交替：第 0、2、4 条（偶数）从左下往右上读；第 1、3 条（奇数）从右上往左下读。一条上、一条下，像蛇形扫描。
- 11一支笔，走一格记一格更好写的办法：直接模拟一支笔。它沿着斜线走，走到矩阵的边界（上下左右某条边）就拐弯换方向。我们一格一格地走给你看。
- 12撞到哪条边，怎么拐笔有「向上」「向下」两种状态。向上时优先斜着走 (行-1,列+1)，但若已贴着上边或右边就得拐；向下同理。先撞右/下边就右移一格，否则撞上/左边就下移一格——记住这四句就不会乱。
- 13读出 1笔从左上角 (0,0) 出发，当前方向「向上」。读下第一个数 1，放进输出序列。注意右边面板，结果会一格一格长出来。
- 14笔走到 (0,1)，读出 2在 (0,0) 想向上走，可它已经贴着最上边了，于是右移一列到 (0,1)，并把方向翻成「向下」。读出 2。(0,0) 变蓝表示读过了。
- 15笔走到 (1,0)，读出 4现在方向「向下」，没撞边，就斜着走一格：行 +1、列 -1，从 (0,1) 到 (1,0)。读出 4。这就是第 1 条对角线（2、4）从上往下读完了。
- 16笔走到 (2,0)，读出 7在 (1,0) 还想向下，可它贴着最左边了，于是下移一行到 (2,0)，方向翻成「向上」。读出 7。第 2 条对角线开始了。
- 17笔走到 (1,1)，读出 5方向「向上」，没撞边，斜着走：行 -1、列 +1，从 (2,0) 到 (1,1)。读出中心的 5。沿着这条最长的斜线往右上爬。
- 18笔走到 (0,2)，读出 3继续向上斜走一格，从 (1,1) 到 (0,2)，读出 3。第 2 条对角线（7、5、3）从下往上读完了。注意输出里它正是这个顺序。
- 19笔走到 (1,2)，读出 6在 (0,2) 想向上，可它撞到了右边（向上时右边优先），于是下移一行到 (1,2)，方向翻成「向下」。读出 6。
- 20笔走到 (2,1)，读出 8方向「向下」，没撞边，斜着走：行 +1、列 -1，从 (1,2) 到 (2,1)。读出 8。第 3 条对角线（6、8）从上往下读完。
- 21笔走到 (2,2)，读出 9在 (2,1) 想向下，撞到了下边，于是右移一列到 (2,2)，方向翻成「向上」。读出最后的 9。9 个数全读完了。
- 22输出 = [1,2,4,7,5,3,6,8,9]这支笔走过的轨迹就是答案：[1,2,4,7,5,3,6,8,9]。整张图只走了一遍，每个格子读一次，干净利落。
- 23d=0/2/4 从下往上回看一下：紫色高亮的是偶数条对角线（d=0、2、4），它们都是从下往上读的——1；7、5、3；9。
- 24d=1/3 从上往下紫色高亮的是奇数条对角线（d=1、3），它们都是从上往下读的——2、4；6、8。和偶数条正好方向相反，这就是「上下交替」。
- 25起点 (0,0) → 终点 (2,2)把这支笔走过的路连起来看：从紫色起点 (0,0) 出发，沿斜线上上下下地翻，最后到红色终点 (2,2)。这条 Z 字轨迹就是对角线遍历的全部秘密。
- 26走 m×n 步，每步记一格再转向代码就是把刚才那支笔写成循环：一共走 m×n 步，每步先把当前格子塞进结果，再根据「向上/向下 + 有没有撞边」算出下一步落点。下面看三语言实现。
- 29记住这一句螺旋矩阵、对角线遍历这类题的共同套路就是「模拟」：想清楚走的方向、什么时候转向，让一支笔老老实实把每个格子走一遍，代码就出来了。
- 31(0,2) 两条边都贴着在右上角 (0,2)（红色），向上走时它既贴右边又贴上边。必须先判右边（下移到 (1,2)）；若先判上边会想右移、列就越界了。这是本题最刁的一格。
⚠️ 容易写错的地方
✗ 错：向上撞边时先判上边、再判右边
✓ 对：向上时先判右边（c==n-1）再判上边（r==0）
在右上角 (0,n-1) 两条边都撞，判错顺序会算出越界的下一步
✗ 错：转向后忘了同时调整行或列，只翻 up
✓ 对：撞边时既翻方向，又要按规则移动一格（右移或下移）
只翻方向不挪格子，笔会原地卡住或重复读同一格
✗ 错：用 i+j 奇偶分组但忘了奇数条要反转
✓ 对：偶数条从下往上、奇数条从上往下，方向必须交替
不交替方向，输出顺序就乱了，过不了样例
完整代码（Python / C++ / Java）
Python
class Solution:
def findDiagonalOrder(self, mat):
if not mat or not mat[0]:
return []
m, n = len(mat), len(mat[0])
res = []
r = c = 0
up = True
for _ in range(m * n):
res.append(mat[r][c])
if up:
if c == n - 1:
r += 1; up = False
elif r == 0:
c += 1; up = False
else:
r -= 1; c += 1
else:
if r == m - 1:
c += 1; up = True
elif c == 0:
r += 1; up = True
else:
r += 1; c -= 1
return resC++
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
if (mat.empty() || mat[0].empty()) return {};
int m = mat.size(), n = mat[0].size();
vector<int> res;
int r = 0, c = 0;
bool up = true;
for (int k = 0; k < m * n; k++) {
res.push_back(mat[r][c]);
if (up) {
if (c == n - 1) { r++; up = false; }
else if (r == 0) { c++; up = false; }
else { r--; c++; }
} else {
if (r == m - 1) { c++; up = true; }
else if (c == 0) { r++; up = true; }
else { r++; c--; }
}
}
return res;
}
};Java
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
if (mat.length == 0 || mat[0].length == 0) return new int[0];
int m = mat.length, n = mat[0].length;
int[] res = new int[m * n];
int r = 0, c = 0;
boolean up = true;
for (int k = 0; k < m * n; k++) {
res[k] = mat[r][c];
if (up) {
if (c == n - 1) { r++; up = false; }
else if (r == 0) { c++; up = false; }
else { r--; c++; }
} else {
if (r == m - 1) { c++; up = true; }
else if (c == 0) { r++; up = true; }
else { r++; c--; }
}
}
return res;
}
}复杂度
时间
O(m·n)
每个格子恰好被访问、读出一次
空间
O(1)
除返回数组外只用 r、c、up 几个变量，原地模拟
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 对角线遍历 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
除了模拟一支笔，还有别的写法吗？+
可以按对角线分组：用哈希或数组把 i+j 相同的元素收到同一组，一共 m+n-1 组；偶数组反转后拼接、奇数组直接拼接。思路更直观，但要额外开分组空间，模拟法空间 O(1) 更省。
如果方向反过来，第一条从上往下读呢？+
把初始 up 设成 false 即可，转向规则完全对称，框架一行都不用改。
为什么向上走要先判右边、向下走要先判下边？+
因为在角落（如右上角、左下角）两条边会同时撞，必须先处理「走的方向上更靠前的那条边」，否则另一条边的移动会让坐标越界。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 对角线遍历 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。