498. 对角线遍历
1. 题目简介
难度：中等，原题链接：498. 对角线遍历。
给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
2. 问题分析
同一条对角线上的元素，行、列下标之和相同。用这个和作为对角线编号，就能逐条枚举，再根据编号的奇偶性决定访问方向。
2.1 对角线编号
对于位置 (x, y)，它位于第 x + y 条对角线上。例如第 0 条只有 (0, 0)，第 1 条包含 (0, 1) 和 (1, 0)。
矩阵有 m 行、n 列，最后一个位置是 (m - 1, n - 1)，因此最大编号为 m + n - 2。编号从 0 开始，一共有 m + n - 1 条对角线。
2.2 每条对角线的范围
第 i 条对角线上，行下标为 x 时，列下标就是 i - x。只要确定行下标的范围，就能找到整条对角线。
先按从左下到右上的方向考虑。起点落在最左列或最下行：
i < m时，起点是(i, 0)。i >= m时，起点是(m - 1, i - (m - 1))。
所以起点的行下标为 startX = Math.min(i, m - 1)。终点落在最上行或最右列，其列下标为 Math.min(i, n - 1)，行下标为 endX = i - Math.min(i, n - 1)。
例如 m = 2、n = 3 时，第 2 条对角线从 (1, 1) 延伸到 (0, 2)。它的行下标就在 endX = 0 与 startX = 1 之间。
2.3 按奇偶调整方向
题目要求相邻对角线的访问方向交替变化。从第 0 条开始：
- 偶数编号从左下到右上，行下标从
startX递减到endX。 - 奇数编号从右上到左下，行下标从
endX递增到startX。
无论方向如何，列下标始终等于对角线编号减去行下标。因此代码用 mat[j][i - j] 读取元素，再依次写入结果数组。
3. 代码实现
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[] res = new int[m * n];
int count = 0;
int t = (m - 1) + (n - 1);
for (int i = 0; i <= t; i++) {
int startX = Math.min(i, m - 1);
int endX = i - Math.min(i, n - 1);
if (i % 2 == 0) {
for (int j = startX; j >= endX; j--) {
res[count++] = mat[j][i - j];
}
} else {
for (int j = endX; j <= startX; j++) {
res[count++] = mat[j][i - j];
}
}
}
return res;
}
public static void main(String[] args) {
int[][] mat = new int[][] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
Solution s = new Solution();
int[] res = s.findDiagonalOrder(mat);
System.out.println(res);
}
}
4. 复杂度分析
- 时间复杂度：O(m × n)，每个元素恰好访问一次。
- 额外空间复杂度：O(1)，不计返回数组；返回数组本身占 O(m × n) 空间。
5. 关联问题
矩阵的各种遍历方式：
来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明