498. Diagonal Traverse

🟠   🔖  数组 矩阵 模拟  🔗 LeetCode

题目

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]

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

Example 2:

Input: mat = [[1,2],[3,4]]

Output: [1,2,3,4]

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 10^4
• 1 <= m * n <= 10^4
• -10^5 <= mat[i][j] <= 10^5

题目大意

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

说明: 给定矩阵中的元素总数不会超过 100000 。

解题思路

• 给出一个二维数组，要求按照如图的方式遍历整个数组。
• 这一题用模拟的方式就可以解出来。需要注意的是边界条件：比如二维数组为空，二维数组退化为一行或者一列，退化为一个元素。具体例子见测试用例。
• 解题关键是在判断下一个位置，将矩阵想像成一个 X,Y 坐标轴。那么可分为以下几种情况， 1、斜角向右上遍历时， 当右上角在坐标轴内， 正常计算 即， x+1(X 轴向右移动)， y-1(Y 轴向上移动) 当右上角在坐标轴外，那么当前位置只能在 第一行 X 坐标轴 ，或者 最后一列 Y 坐标轴，即判断该两种情况下，应该 X 坐标往右，或者 Y 坐标往上 2、同理 斜角向下遍历时 当左下角在坐标轴内，正常计算 即， x-1(X 轴向右移动)， y+1(Y 轴向下移动) 当左下角在坐标轴外，那么当前位置只能在 第一列 Y 坐标轴，或者 最后一行 X 坐标轴，即判断该两种情况下，应该 X 坐标往左，或者 Y 坐标往下

代码

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
var findDiagonalOrder = function (mat) {
  const rowLen = mat.length;
  const colLen = mat[0].length;
  const total = rowLen * colLen;
  const result = [];
  let k = 0;
  let row = 0;
  let col = 0;
  let direction = "up";

  while (k < total) {
    result.push(mat[row][col]);

    if (direction === "up") {
      if (row === 0 && col < colLen - 1) {
        col++;
        direction = "down";
      } else if (col === colLen - 1) {
        row++;
        direction = "down";
      } else {
        row--;
        col++;
      }
    } else {
      if (col === 0 && row < rowLen - 1) {
        row++;
        direction = "up";
      } else if (row === rowLen - 1) {
        col++;
        direction = "up";
      } else {
        row++;
        col--;
      }
    }
    k++;
  }
  return result;
};

相关题目

相关题目

• 2075. 解码斜向换位密码

- [2075. 解码斜向换位密码](https://leetcode.com/problems/decode-the-slanted-ciphertext)