498.diagonal-traverse.md

算法思路

模拟遍历过程：

对角线遍历，斜率为 1，方程为 i + j = k, k 为截距，截距的取值范围为 [0, M + N - 1)

i 取值范围为 [0, M - 1], j 取值范围为 [0, N - 1] 当 i % 2 == 0时， i 从 大 到 小 遍历， 当 i % 2 == 1时， j 从 大 到 小 遍历

代码实现

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] res = new int[m * n];
        // ud: 对角线截距，si: 斜向上i 的起始位置，sj:斜向下j的起始位置，k: 结果数组下标
        for (int ud = 0, si = 0, sj = 1, k = 0; ud < m + n - 1; ud++) {
            if ((ud & 1) == 0) { // 斜向上
                for (int i = si; i >= 0; i--) {
                    int j = ud - i;
                    if (j < 0 || j >= n) continue;
                    res[k++] = mat[i][j];
                }
                si = Math.min(si + 2, m - 1);
            } else { // 斜向下
                for (int j = sj; j >= 0; j--) {
                    int i = ud - j;
                    if (i < 0 || i>=m) continue;
                    res[k++] = mat[i][j];
                }
                sj = Math.min(sj + 2, n - 1);
            }
        }
        return res;
    }
}