Leetcode498. 对角线遍历

题目描述

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

示例:

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

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

解释：

说明:

  1. 给定矩阵中的元素总数不会超过 100000 。

解题思路

这道题只需要模拟就可以了。这道题需要做的是三部分：一个是变向，一个是怎么对角移动坐标，最后一个是怎么处理边界条件。

先说变向问题，这个很好处理。首先用一个变量direction指示方向，1表示向右上角移动，0表示向左下角移动，然后变向的操作可以用direction = 1 - direction完成。

接下来就是对角移动。这个也很容易观察出规律：

右上角：

[row, col] -> [row - 1, col + 1]

newRow = row - 1;

newCol = col + 1;

左下角：

[row, col] -> [row + 1, col - 1]

newRow = row + 1;

newCol = col - 1;

然后就是最为麻烦的边界条件处理。

首先是进行边界条件处理的条件是对角移动后坐标超出数组范围：

1
newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols

在往右上角移动的时候，可能到达上面的边界(col < cols - 1)或者右边的边界(col == cols - 1)。对这个需要进行分别的处理。当到达上面的边界的时候，col += 1；当到达右边的边界的时候，row += 1。

在往左下角移动的时候，可能到达下面的边界(row == rows - 1)或者左边的边界(row < rows - 1)。对这个也需要进行分别的处理。当到达下面的边界的时候，col += 1；当到达左边的边界的时候，row += 1。

最后还需要考虑以下什么时候退出循环。经过观察，发现不满足下面条件的时候推出就可以：

1
row < rows && col < cols

将上面列出的综合起来，就可以得到相关的代码。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
vector<int> findDiagonalOrder(vector<vector<int>>& mat){
    if(mat.empty()) return {};

    int rows = mat.size();
    int cols = mat[0].size();
    int row = 0, col = 0;
    int direction = 1;
    vector<int> result;

    while(row < rows && col < cols){
        result.emplace_back(mat[row][col]);

        int newRow = row + (direction == 1 ? -1 : 1);
        int newCol = col + (direction == 1 ? 1 : -1);

        if(newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols){
            if(direction == 1){
                if(col < cols - 1){
                    col += 1;
                }
                else if(col == cols - 1){
                    row += 1;
                }
            }else{
                if(row < rows - 1){
                    row += 1;
                }
                else if(row == rows - 1){
                    col += 1;
                }
            }
            direction = 1 - direction;
        }else{
            row = newRow;
            col = newCol;
        }
    }
    return result;
}

复杂度分析

时间复杂度：O(rows⋅cols)O(rows \cdot cols)​

空间复杂度：O(1)O(1)​，不考虑输入输出所需要的空间​