498.对角线遍历 (Medium)*

题目描述*

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

示例*

输入:

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

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

代码*

每条对角线上 i + j 不变，遍历过程中和递增。

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if(matrix.size() == 0 || matrix[0].size() == 0) {
            return res;
        }
        int m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < m + n - 1; i++) {
            if((i & 1) == 0) {
                int x = ((i < m) ? i : m - 1);
                int y = i - x;
                while(x >= 0 && y < n) {
                    res.push_back(matrix[x--][y++]);
                }
            }else {
                int y = ((i < n) ? i : n - 1);
                int x = i - y;
                while(x < m && y >= 0) {
                    res.push_back(matrix[x++][y--]);
                }
            }
        }
        return res;

    }
};

最后更新: July 23, 2022