498. 对角线遍历
1. 题目简介
难度：中等，原题链接：498. 对角线遍历。
给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
2. 问题分析
一道模拟的题目，只要能够模拟出对角线遍历的过程，就可以解出这道题目。
为了简化遍历的复杂度，我们需要先找到对角线遍历的规律。
2.1. 对角线遍历转化为层级遍历
如果把每一个对角线都当作一层来看的话，那么这道题目就变成了找到每一层遍历的起点与方向
按照这一思路，继续观察每一层级的节点，可以发现层级的开始或者结束都会落在最左一列与最下一行，因此可以计算出总的层级数量是 （m - 1） + （n - 1）
继续观察每一个层级，会发现，每一层的横纵坐标和总是与所在的层级数相同，也就是对于第 i 层的起点 start[x][y]，有 x + y = i。比如：
- 第 0 层只有
[0, 0]这一个点, 横纵坐标和为0 - 第 1 层有
[0, 1]与[1, 0]两个点, 横纵坐标和为1 - 以此类推
2.2. 遍历每一个层级
接下来我们要遍历每一个层级。首要问题就是找到遍历的起点与终点。
为了简化遍历的复杂度，我们可以先假设所有层级的遍历都是从左下到右上的。那么所有的起点一定会落在最左一列与最下一行。
对于第 i 层的起点 start[x][y]，它所在的位置有两种情况:
- 起点在最左侧的一列，也就是
y = 0，那么起点为[i, 0] - 起点在最下侧的一行，也就是
x = m - 1，那么起点为[m - 1, i - (m - 1)]
这主要取决于起点是落在最左一列还是最下一行。也就是说，如果 i < m，那么起点为 [i, 0]，否则起点为 [m - 1, i - (m - 1)]。
可以确定起点的横坐标为 start[x] = Math.min(i, m - 1)，即到达最左下角的位置时，剩下层级的起点会沿着最下一行向右侧移动。
同样的思路我们也可以找到终点的横坐标 end[x] = i - Math.min(i, n - 1)。
2.3. 调整遍历顺序
在上一步中，为了简化遍历的复杂度，我们假设了所有层级的遍历都是从左下到右上的。
接下来要模拟真实的遍历规则了。
可以发现，层级遍历的方向与层级数奇偶性有关。如果从第 0 层开始排序的话，那么对于层数 t 来说：
- 当
t % 2 == 0时，遍历方向为左下到右上 - 当
t % 2 == 1时，遍历方向为右上到左下
因此，我们可以根据层级数 t 的奇偶性来调整遍历的方向。
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(n)，每个元素都遍历了一遍。
- 空间复杂度：O(1)，没有使用额外的空间。
5. 关联问题
矩阵的各种遍 历方式：