498. 对角线遍历.md

498. 对角线遍历

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

示例:

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

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

解释:

说明:

1. 给定矩阵中的元素总数不会超过 100000 。

思路

1、假设1个坐标为 matrix[row][col]， 在一次对角线遍历时，row+col 的值是相等的

2、当row递增时，col的递减的，反之亦然

3、在遍历完一次斜角时，要反转row，col的单调性

4、确定row和 col 的临界点

代码

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var findDiagonalOrder = function(matrix) {
  let rowLen = matrix.length, colLen = matrix[0] && matrix[0].length;
  const res = [];
  if (!rowLen || !colLen) return res;
  let flag = true;

  for(let i = 0; i < rowLen + colLen; i ++) {
    let endRow = flag ? rowLen : colLen;
    let endCol = flag ? colLen : rowLen;

    let row = (i < endRow) ? i : endRow - 1;
    let col = i - row;

    while(row >= 0 && col < endCol) {{
      res.push(flag ? matrix[row][col] : matrix[col][row]);
      row--;
      col++;
    }}
    flag = !flag;
  }
  return res;
};

复杂度分析

时间复杂度 $O(row * col)$

空间复杂度 $O(1)$