对角线遍历

说在前面

🎈每天进行一道算法题目练习，今天的题目是“对角线遍历”。

问题描述

给你一个大小为 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

思路分析

题目的描述很简单，要求也很简单，就是给定一个 m * n 的矩阵，要我们输出按对角线遍历的结果，遍历的规则如示例1所示，从左上角出发，先向右上遍历，再向左下遍历，交替遍历直到遍历完所有元素，读完题目后我们知道了题目要求，接下来就是要根据规律来输入结果。

如图所示，图中是一个 8 * 7 的矩阵，我们可以看到其中对角线的数量为14条，这数量与m和n之间有什么关联吗？我们可以继续看下图：

通过上图我们可以看出每一条对角线都会经过左边和下边方块的左下顶点，所以我们只需要计算这两边的左下顶点数即可得出矩阵的对角线数量为：m + n - 1,而且对角线的方向是交叉的，如上图，我们可以从左往右给每条对角线排个序，我们可以发现序号是奇数时的对角线的方向为从左下到右上，偶数时则相反，方向为由右上到左下。确定方向后我们还需要知道对角线的起点和终点，观察上图我们可以发现：

• 1、对角线序号为奇数

奇数时对角线的起始点应该在左边或者下边
（1）起始点在左边时
起始点在左边时，起始点的行数与序号相等，列数为0；
（2）起始点在下边时
起始点在下边时，起始点的行数为m，列数为序号减去m。

• 2、对角线序号为偶数

奇数时对角线的起始点应该在上边或者右边
（1）起始点在上边时
起始点在左边时，起始点的行数为0，列数与序号相等；
（2）起始点在下边时
起始点在下边时，起始点的行数为序号减去n，列数为n。

确定了起点之后我们可以开始获取对角线上的每一个点：

• 1、对角线序号为奇数

对角线序号为奇数，即其对角线方向为左下到右上，对角线上的点应该满足以下规律

p[i] = mat[x][y];
p[i - 1] = mat[x+1][y-1];

• 2、对角线序号为偶数

对角线序号为偶数，即其对角线方向为右上到左下，对角线上的点应该满足以下规律

p[i] = mat[x][y];
p[i - 1] = mat[x-1][y+1];

AC代码

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
 var findDiagonalOrder = function(mat) {
    let res = [];
    const m = mat.length,n = mat[0].length;
    for(let i = 0; i < m + n - 1; i++){
        if(i % 2 == 0){
            let x = i < m ? i : m - 1;
            let y = i < m ? 0 : i - m + 1;
            while (x >= 0 && y < n) {
                res.push(mat[x--][y++]);
            }
        }else {
            let x = i < n ? 0 : i - n + 1;
            let y = i < n ? i : n - 1;
            while (x < m && y >= 0) {
                res.push(mat[x++][y--]);
            }
        }
    }
    return res;
};

说在后面

🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。