LeetCode 每日一题 [37] 对角线遍历

LeetCode 对角线遍历 [中等]

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

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

输入:

[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,4,7,5,3,6,8,9]
解释:

1

题目分析

解法1

1.前三行，最基本的判断还是要有的，避免多余循环
2.假设横为x，竖为y，此题求解换个思路相当于求x，y
3.沿对角线遍历，那必然是x--，y++（自上而下）或y--，x++（自下而上）
4.转弯处注意边界值判断

代码实现

public class LeetCode_01_FindDiagonalOrder {
    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int[] diagonalOrder = findDiagonalOrder(matrix);
        System.out.println(Arrays.toString(diagonalOrder));
    }

    public static int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return new int[]{};
        }
        if (matrix.length == 1) {
            return matrix[0];
        }
        int size = matrix.length * matrix[0].length;
        int[] res = new int[size];
        int x = 0;
        int y = 0;
        //true 表示向右上角遍历 false表示向左下角遍历
        boolean flag = true;
        for (int i = 0; i < size; i++) {
            res[i] = matrix[x][y];
            if (flag) {
                x--;
                y++;

                //判断边界值
                if (y > matrix[0].length - 1) {
                    y = matrix[0].length - 1;
                    x += 2;
                    flag = false;
                }
                //判断边界值
                if (x < 0) {
                    x = 0;
                    flag = false;
                }
            } else {
                x++;
                y--;
                //边界值判断
                if (x > matrix.length - 1) {
                    x = matrix.length - 1;
                    y += 2;
                    flag = true;
                }
                if (y < 0) {
                    y = 0;
                    flag = true;
                }
            }
        }
        return res;
    }
}