1.题目

题目地址(498. 对角线遍历 - 力扣（LeetCode）)

https://leetcode.cn/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 == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• -105 <= mat[i][j] <= 105

2.题解

2.1 模拟

注意一下向右是y+1, 向下是x+1, 最开始弄反了, 导致我弄了好久没弄出来!!!
这里关键点是知道一条对角线触碰到边界后, 下一次的起始点!!! 通过下图我们能发现规律

1. 如果上一次是向右上截止(本次是左下方向), 那么优先级是首先找是否有(x,y+1), 如果没有选择(x+1, y)
2. 如果上一次是向左下截止(本次是右上方向), 那么优先级是首先找是否有(x+1,y), 如果没有选择(x, y+1)

对角线方向遍历, 我们设置一个方向数组dir即可{{-1, 1}(右上), {1, -1}(左下)}
对于碰壁后出发点转变, 我们新设置一个出发点变更数组 trans(按上方的优先级即可) 即可; 这里要判断两次, 第一次是判断按对角线方向走是否碰壁, 第二次是判断高优先级出发点是否存在,不存在就选择次级优先级出发点.

代码

• 语言支持：C++

C++ Code:

class Solution {
	public:
		vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
			int row = mat.size(), col = mat[0].size();
			vector<pair<int, int>> dir{{-1, 1},{1, -1}}; // 分别对应右上, 左下方向
			vector<pair<int, int>> trans{{0, 1},{1, 0}}; // cnt=0(右上方向时,下次左下), 优先{0, 1}; cnt=1(左上方向时,下次右上), 优先 {1, 0}; (cnt+1)%2表示次级优先
			vector<int> ans;
			int cnt = 0, x = 0, y = 0;
			for(int i = 0; i < row * col; i++) {
				ans.push_back(mat[x][y]);
                // 按对角线方向行走
				int dx = x + dir[cnt].first; 
				int dy = y + dir[cnt].second;
                // 按对角线走碰壁
				if(dx < 0 || dx >= row || dy < 0 || dy >= col) {
					dx = x + trans[cnt].first;
					dy = y + trans[cnt].second;
                    // 高优先级出发点不存在, 选择次级优先级出发点
					if(dx < 0 || dx >= row || dy < 0 || dy >= col) {
						dx = x + trans[(cnt+1)%2].first;
						dy = y + trans[(cnt+1)%2].second;
					}
					cnt = (cnt+1) % 2; // 转变对角线行走方向
				}
                // 更新 x, y值
				x = dx;
				y = dy;
			}
			return ans;
		}
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：\(O(n)\)
• 空间复杂度：\(O(n)\)