【模拟】对角线遍历

题目

498. 对角线遍历

---

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

示例 1：

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

示例 2：

输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 10^4
• 1 <= m * n <= 10^4
• -10^5 <= mat[i][j] <= 10^5

解题

方法一：模拟

思路

根据题意直接模拟，在奇数对角线从左下向右上遍历，偶数对角线从右上向左下遍历。

维护一个布尔值为 true 表示当前是奇数对角线，为 false 时表示当前是偶数对角线，在每次走到边界进入下一条对角线时切换状态。

由该图可知：

• 奇数对角线：
  • 正常情况下: x-- y++
  • 边界情况1: x==0 时 y++
  • 边界情况2: y==n-1 时 x++
• 偶数对角线：
  • 正常情况下: x++ y--
  • 边界情况1: y==0 时 x++
  • 边界情况2: x==m-1 时 y++

而在矩阵是正方形时遍历正方形对角线的这一趟会出现两种边界情况同时成立的情况，这时候就需要决定判断的先后顺序了。

如图可以很明显的看出来。

代码

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] ans = new int[m * n];
        int x = 0, y = 0;
        boolean flag = true;
        for (int i = 0; i < m * n; i++) {
            ans[i] = mat[x][y];
            if (flag) {
                if (y + 1 == n) {
                    x++;
                    flag = !flag;
                } else if (x == 0) {
                    y++;
                    flag = !flag;
                } else {
                    x--;
                    y++;
                }
            } else {
                if (x + 1 == m) {
                    y++;
                    flag = !flag;
                } else if (y == 0) {
                    x++;
                    flag = !flag;
                } else {
                    x++;
                    y--;
                }
            }
        }
        return ans;
    }
}

另一种方法判断对角线状态：

找规律我们会发现：

对角线1   (0, 0)                 x + y = 0
对角线2   (0, 1) (1, 0)          x + y = 1
对角线3   (2, 0) (1, 1) (0, 2)   x + y = 2
对角线4   (1, 2) (2, 1)          x + y = 3
对角线5   (2, 2)                 x + y = 4

我们可以很明显的发现横纵坐标相加为偶数时是↗遍历，为奇数时是↙遍历。

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] ans = new int[m * n];
        int x = 0, y = 0;
        for (int i = 0; i < m * n; i++) {
            ans[i] = mat[x][y];
            if (((x + y) & 1) == 0) {
                if (y + 1 == n) x++;
                else if (x == 0) y++;
                else {
                    x--;
                    y++;
                }
            } else {
                if (x + 1 == m) y++;
                else if (y == 0) x++;
                else {
                    x++;
                    y--;
                }
            }
        }
        return ans;
    }
}