498.对角线遍历

题目

对角线遍历

思路

进行模拟，有向右上和左下两个方向的区别。分别找出在边界需要改变的坐标方法。

题解

• 题解1

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        int x = 0, y = 0;
        vector<int> res;
        int row = mat.size(), col = mat[0].size();
        bool flag = true;
        while(true){
            cout << x << "," << y << "      " << flag << endl;
            res.push_back(mat[x][y]);
            if (x == row - 1 && y == col - 1 ) break;
            else if(flag) {  // flag 为true时向右上角
                if(y == col - 1){
                    x ++;
                    flag = false;
                }
                else if(x == 0) {
                    y ++;
                    flag = false;
                } else {
                    x --;
                    y ++;
                }
                
            } else {
                if(x == row - 1) {
                    y ++;
                    flag = true;
                }
                else if (y == 0) {
                    x ++;
                    flag = true;
                }
                else {
                    x ++;
                    y --;
                }
            }
            
        }
        return res;
    }
};

• 时间复杂度：O(n + m)，其中 n 是数组行数，m是数组列数
• 空间复杂度：O(1)

执行用时：104 ms, 在所有 C++ 提交中击败了8.27%的用户

内存消耗：17.8 MB, 在所有 C++ 提交中击败了78.97%的用户

通过测试用例：32 / 32