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.前三行，最基本的判斷還是要有的，避免多余循環(huán)
2.假設(shè)橫為x，豎為y，此題求解換個思路相當(dāng)于求x，y
3.沿對角線遍歷，那必然是x--，y++（自上而下）或y--，x++（自下而上）
4.轉(zhuǎn)彎處注意邊界值判斷

代碼實現(xiàn)

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;
    }
}