LeetCode 对角线遍历

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

示例:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

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

题解

改解法的关键在于确定每一层的坐标范围，其中下边界low = Math.max(0, i - n + 1)，这样可以保证下边界不会小于0，而上边界high = Math.min(i, m - 1)，这样也保证了上边界不会大于m-1，如果是偶数层，则从上边界往下边界遍历，反之如果是奇数层，则从下边界往上边界遍历

class Solution {
    public int[] findDiagonalOrder(int[] matrix) {
        if (matrix.length == 0) {
            return new int[0];
        }
        int M = matrix.length;
        int N = matrix[0].length;
        int[] result = new int[M * N];
        int k = 0;
        // 对角线的层数
        for (int i = 0; i < M + N - 1; i++) {
            int low = Math.max(0, i - N + 1);
            int high = Math.min(i, M - 1);
            // 判别方向
            if (i % 2 == 0) {
                for (int j = high; j >= low; j--) {
                    result[k++] = matrix[j][i - j];
                }
            } else {
                for (int j = low; j <= high; j++) {
                    result[k++] = matrix[j][i - j];
                }
            }
        }
        return result;
    }
}