498. 对角线遍历

🟠   🔖  数组 矩阵 模拟  🔗 力扣 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	解码斜向换位密码		字符串 模拟