LeetCode_模拟_中等_498.对角线遍历

1.题目

给你一个大小为 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⁴
1 <= m * n <= 10⁴
-10⁵ <= mat[i][j] <= 10⁵

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/diagonal-traverse

2.思路

（1）模拟
① 首先，分析题目可知，在整个遍历过程中，只有两种遍历方向：右上方和左下方；
② 在朝右上方遍历时，如果遍历到边界（例如示例 1 中的元素 1 和 3）：此时先判断当前元素的右侧相邻元素的位置是否越界，如果未越界，则遍历该元素，并且切换遍历方向；如果越界，则选择当前元素的下侧相邻元素，同时也要切换遍历方向。
③ 在朝左下方遍历时，其步骤与朝右上方遍历类似，此处不再赘述。
④ 需要注意的是，由于在遍历过程中遍历方向有所不同，所以我们可能通过 boolean 变量 flag 来表示遍历方向，例如 flag = true 表示方向为右上方。此外，该方法的时间复杂度为 O(m * n)。

3.代码实现（Java）

//思路1————模拟
class Solution {
    
    public int[] findDiagonalOrder(int[][] mat) {
    
        // m 行 n 列的矩阵
        int m = mat.length;
        int n = mat[0].length;
        // res 保存最终的结果
        int[] res = new int[m * n];
        /* 遍历方向只有两种：右上方和左下方 刚开始的方向是右上方，将 flag 设置为 true 那么 flag = false 表示方向为左下方 */
        boolean flag = true;
        //从矩阵的左上角第一个元素开始遍历
        int i = 0, j = 0;
        //以对角线遍历方式开始遍历矩阵
        for (int k = 0; k < m * n; k++) {
    
            res[k] = mat[i][j];
            //右上方
            if (flag) {
    
                //下一个元素的位置
                int x = i - 1, y = j + 1;
                //如果 x、y 超过了边界，则需要变换方向
                if (x < 0 || y >= n) {
    
                    // (1) 下一个元素是右边相邻元素
                    x = i;
                    y = j + 1;
                    if (x < 0 || y >= n) {
    
                        // (2) 下一个元素是下边相邻元素
                        x = i + 1;
                        y = j;
                    }
                    //变换方向
                    flag = false;
                }
                // i、j 替代下一个元素的位置
                i = x;
                j = y;
            } else {
    
                //左下方，这里的处理与右上方类似
                int x = i + 1, y = j - 1;
                //判断边界
                if (x >= m || y < 0) {
    
                    x = i + 1;
                    y = j;
                    if (x >= m || y < 0) {
    
                        x = i;
                        y = j + 1;
                    }
                    //变换方向
                    flag = true;
                }
                i = x;
                j = y;
            }
        }
        return res;
    }
}