LeetCode 498. 对角线遍历

题目描述：

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

示例：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]
1
2

思路：

一个矩阵，假设共有n行，m列，则其对角线（指的是/这种方向的对角线，而不是\）一共有n + m - 1条。假设对角线编号从0开始，则所有对角线的编号范围则是[0,n + m - 2]，并且容易得到一个性质，编号为i的对角线上的点，其横纵坐标之和等于i。

观察数据样例可知：编号i为偶数的对角线，遍历方向是从左下到右上；编号i为奇数的对角线，遍历方向是从右上到左下。

从左下到右上，点的坐标的变化是，行数减1，列数加1。即x--，y++

从右上到左下，点的坐标的变化是，行数加1，列数减1,。即x++，y--

当一条对角线遍历完成后，我们需要找到下一个点作为起点，并翻转遍历方向。

找到下一个点作为起点，可以分情况讨论。

设当前遍历的对角线的编号为i

• 当方向是从左下到右上时
  • 当i < m - 1时，下一个起点的列，一定是i + 1，即 y = i + 1，而行，可以直接根据根据对角线上所有点的横纵坐标是个常数，来算出来，即x = (i + 1) - y
  • 当i >= m - 1时，下一个起点的列，只能到最后一列，即y = m - 1，而x = (i + 1) - y
• 当方向是从右上到左下时
  • 当i < n - 1时，下一个起点的行，一定是i + 1，即x = i + 1，而y = (i + 1) - x
  • 当i >= n - 1时，下一个起点的行，只到最后一行，即x = n - 1，而y = (i + 1) - x

class Solution {
    // 重要性质: 同一条对角线上的点, 其[x,y]坐标的和是固定的
    // 对角线条数, 总共 m + n - 1 条
    // 第 i 条对角线上的坐标的和为 i
    // 和为偶数, 向右上角走 (x--, y++)
    // 和为奇数, 向左下角走 (x++, y--)
    public int[] findDiagonalOrder(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int[] ans = new int[n * m];
        int k = 0;
        int x = 0, y = 0;
        for (int i = 0; i < n + m - 1; i++) {
           if ((i & 1) == 0) {
               // 把这条线走到头
               while (x >= 0 && y < m) ans[k++] = mat[x--][y++];
               if (i < m - 1) y = i + 1;
               else y = m - 1;
               x = i + 1 - y;
           } else {
               while (x < n && y >= 0) ans[k++] = mat[x++][y--];
               if (i < n - 1) x = i + 1;
               else x = n - 1;
               y = i + 1 - x;
           }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28