498. Diagonal Traverse
498. Diagonal Traverse
题目
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;
};