Leetcode 498.对角线遍历

498.对角线遍历

498.对角线遍历

• 标签：数组、矩阵、模拟

• 难度：中等

描述：给定一个大小为 m×n 的矩阵 mat 。

要求：以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

说明：

• m == mat.length

• n == mat[i].length

• 1 <= m, n <= 10^4

• 1 <= m * n <= 10^4

• -10^5 <= mat[i][j] <= 10^5

示例：

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

思路

本题思路是找规律+边界条件。

首先要求按照对角线遍历，对角线上元素的特征是 行下标 + 列下标之和等于某个值。仔细看图，其实对角线遍历还存在2个方向：右上到左下、左下到右上。

找规律是要找出对角线2种遍历方向的规律，假设元素在mat矩阵中的坐标是 (x, y)，我们发现：

• 当 x + y 为偶数时候，对角线的方向是从左下到右上，如图中红色线。左下到右上方向上的元素，一般性规则是：x-1, y+1，如数字“7”到“5”。

• 当 x + y 为奇数时候，对角线的方向是从右上到左下，如图中黄色线。右上到左下方向上的元素，一般性规则是：x+1, y-1，如数字“2”到“4”。

对角线无论是右上到左下，还是左下到右上，当遍历到边界时候，都需要转换方向，比如数字“3”下一个访问的是数字“6”，数字“8”下一个访问的是“9”。

对角线方向是左下到右上时候，趋势是 (x-1, y+1)，很容易想到边界情况有2种：

1. 当访问的元素在最后1列，下一步应该 x+1 访问下一个元素。例如：数字“3”到“6”

2. 当访问的元素在第1行，下一步应该 y+1 访问下一个元素。例如：数字“1”到“2”。

其他的情况就是按照一般性规则就是 (x-1, y+1)。特别注意的是，边界情况应该先判断元素是否在最后1列，然后再判断是否在第1行。例如：数字“3”同时是第1行，也是最后1列，但是下一步 x+1 才能访问到数字“6”。

同样地，对角线方向是右上到左下时候，趋势是 (x+1, y-1)，很容易想到边界情况有2种：

1. 当访问的元素在最后1行，下一步应该 y+1 访问下一个元素。例如：数字“8”到“9”

2. 当访问的元素在第1列，下一步应该 x+1 访问下一个元素。例如：数字“4”到“5”。

其他的情况就是按照一般性规则就是 (x+1, y-1)。特别注意的是，边界情况应该先判断元素是否在最后1行，然后再判断是否在第1列。例如：下图中，mat是一个 2x2 的矩阵。数字“4”同时是第1列，也是最后1行，但是下一步 y+1才能访问到数字“5”。

public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[] res = new int[m * n];
        int count = 0;
        int x = 0, y = 0;
        while (count < m * n){
                res[count++] = mat[x][y];
                // 矩阵的行和列之和为偶数，方向：左下方->右上方
                if ( (x + y) % 2 == 0){
                        // 元素所在最后1列，指针下一步 x+1 访问
                        if (y == n-1){
                                x++;
                        }
                        // 元素所在第1行，指针下一步 y+1 访问
                        else if (x == 0){
                                y++;
                        }
                        // 其他情况：指针下一步 x-1, y+1访问
                        else {
                                x--;
                                y++;
                        }
                }
                // 矩阵的行和列之和为奇数，方向：右上方 -> 左下方
                else {
                        // 元素所在最后1行，指针下一步 y+1 访问
                        if (x == m - 1){
                                y++;
                        }
                        // 元素所在第1列，指针下一步 x+1 访问
                        else if (y == 0){
                                x++;
                        }
                        // 其他情况：指针下一步 x+1, y-1访问
                        else{
                                x++;
                                y--;
                        }
                }

        }
        return res;
}

498.对角线遍历 题解