498. 对角线遍历
题目描述
输入 m x n 的矩阵 mat。
按对角线方向以之字形走遍整个矩阵：从左上角 mat[0][0] 出发，先沿右上方向走完第一条对角线，再换到下一条对角线沿左下方向走，此后方向在相邻对角线之间交替。这里的对角线指行号加列号相同的那些格子。
返回按这个顺序依次访问到的元素组成的数组。
示例 1
输入：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，方向交替。
示例 2
输入：mat = [[1,2],[3,4]] 输出：[1,2,3,4]
解释：依次读出 1、2,3、4。
数据范围
m == mat.lengthn == mat[i].length1 <= m, n <= 10^41 <= m * n <= 10^4-10^5 <= mat[i][j] <= 10^5
解题思路
同一条反对角线上的格子满足 i + j = d，d 从 0 到 m+n-2。d 为偶数时往右上走：i 从 min(d, m-1) 开始递减，列 j = d - i；d 为奇数时往左下走：j 从 min(d, n-1) 开始递减，行 i = d - j。循环条件同时检查另一坐标不越界。
为什么正确
处理第 d 条对角线时，res 中恰好是所有 i + j < d 的格子，按题目要求的顺序排列。
复杂度分析
时间 O(m·n)，每个格子恰好访问一次；除结果外额外空间 O(1)。
易错点
起点不能直接取 i = d：当 d ≥ m 时行会越界，要取 min(d, m-1)；同时循环条件还要检查 d - i < n，否则列会越界。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
m, n = len(mat), len(mat[0])
res = []
for d in range(m + n - 1):
if d % 2 == 0:
i = min(d, m - 1)
while i >= 0 and d - i < n:
res.append(mat[i][d - i])
i -= 1
else:
j = min(d, n - 1)
while j >= 0 and d - j < m:
res.append(mat[d - j][j])
j -= 1
return resclass Solution {
public int[] findDiagonalOrder(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[] res = new int[m * n]; int k = 0;
for (int d = 0; d < m + n - 1; d++) {
if (d % 2 == 0) {
int i = Math.min(d, m - 1);
while (i >= 0 && d - i < n) {
res[k++] = mat[i][d - i];
i--;
}
} else {
int j = Math.min(d, n - 1);
while (j >= 0 && d - j < m) {
res[k++] = mat[d - j][j];
j--;
}
}
}
return res;
}
}class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<int> res;
for (int d = 0; d < m + n - 1; d++) {
if (d % 2 == 0) {
int i = min(d, m - 1);
while (i >= 0 && d - i < n) {
res.push_back(mat[i][d - i]);
i--;
}
} else {
int j = min(d, n - 1);
while (j >= 0 && d - j < m) {
res.push_back(mat[d - j][j]);
j--;
}
}
}
return res;
}
};func findDiagonalOrder(mat [][]int) []int {
m, n := len(mat), len(mat[0])
res := []int{}
for d := 0; d < m+n-1; d++ {
if d%2 == 0 {
i := min(d, m-1)
for i >= 0 && d-i < n {
res = append(res, mat[i][d-i])
i--
}
} else {
j := min(d, n-1)
for j >= 0 && d-j < m {
res = append(res, mat[d-j][j])
j--
}
}
}
return res
}var findDiagonalOrder = function(mat) {
const m = mat.length, n = mat[0].length;
const res = [];
for (let d = 0; d < m + n - 1; d++) {
if (d % 2 === 0) {
let i = Math.min(d, m - 1);
while (i >= 0 && d - i < n) {
res.push(mat[i][d - i]);
i--;
}
} else {
let j = Math.min(d, n - 1);
while (j >= 0 && d - j < m) {
res.push(mat[d - j][j]);
j--;
}
}
}
return res;
};function findDiagonalOrder(mat: number[][]): number[] {
const m = mat.length, n = mat[0].length;
const res: number[] = [];
for (let d = 0; d < m + n - 1; d++) {
if (d % 2 === 0) {
let i = Math.min(d, m - 1);
while (i >= 0 && d - i < n) {
res.push(mat[i][d - i]);
i--;
}
} else {
let j = Math.min(d, n - 1);
while (j >= 0 && d - j < m) {
res.push(mat[d - j][j]);
j--;
}
}
}
return res;
}