题目链接

https://leetcode-cn.com/problems/diagonal-traverse/

题目描述

给你一个大小为 m x n 的矩阵 mat,请以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。


遍历路径
遍历路径


示例

示例 1:

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

示例 2:

输入: mat = [[1, 2], [3, 4]]
输出: [1, 2, 3, 4]

题解

根据题目描述不难分析出遍历对角线的元素时,偶数列为反方向遍历,奇数列为正方向遍历,如果全使用正方向遍历,则存储偶数列的数组只需要做翻转就可以更正顺序。


正方向遍历
正方向遍历


已知矩阵共有 m 行和 n 列,通过正方向遍历图可知总共的遍历次数为 $m + n - 1$ 次,其中到达拐点 $n - 1$ 之前,row 一直为 0,列 col 递增,拐点之后,col 不变,row 开始递增。

在每次遍历时要沿着对角线的方向找到对角线上的所有元素,如果当前项为 $mat[row][col]$,则对角线的下一项为 $mat[row + 1][col - 1]$,直到边界。

通过上图不难看出,边界条件限制的其实是 rowcol 的值,col 不能小于 0row 不能大于等于 m


偶数列翻转
偶数列翻转


当偶数列对角线所有项都遍历后保存,并对保存的列表进行翻转,再依次合并进最终的结果中就可以完成对角线遍历输出结果的顺序要求,实现代码如下:

const findDiagonalOrder = (mat) => {
  const result = [];
  const m = mat.length;
  const n = mat[0].length;
  const index = n - 1;
  let row = 0;
  let col = 0;

  for (let i = 0; i < m + n - 1; i++) {
    const diagonal = [];
    const inflexed = i > index;
    row = inflexed ? i - index : 0;
    col = inflexed ? index : i;

    while (row < m && col >= 0) {
      diagonal.push(mat[row][col]);
      row++;
      col--;
    }

    if (i % 2 === 0) {
      diagonal.reverse();
    }

    result.push(...diagonal);
  }

  return result;
}

复杂度分析:

  • 时间复杂度:由于矩阵的每一个点都遍历到,并且不存在重复遍历,所以时间复杂度为 $O(m * n)$
  • 空间复杂度:由于存储对角线元素的个数最大为 mn 的最小值,空间复杂度为 $O(min(m, n))$