【C++】【leetcode.498】对角线遍历

闲来无事刷刷leetcode
498对角线遍历

遍历时只有两种状态：斜对角线往上遍历和斜对角线往下遍历

用一个bool遍历up表示当前的状态，如果up = 1表示正在往上遍历，反之往下遍历。

分别用i表示行坐标，j表示列坐标，向上遍历时如果i - 1 < 0 || j + 1 >= n此时超出边界，那么up = 0，且切换到斜向下遍历时的坐标，如果是列超出边界，那么要跳转到正下方的数，如果是列没有超出边界，跳转到右边的数。

斜对角线往下遍历同理。

时间复杂度： O ( m ∗ n ) O(m*n) O(m∗n)，针对二维数组而言，是线性时间可以完成。空间复杂度等同于二维数组大小。

class Solution {
public:
    vector findDiagonalOrder(vector>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        if(m == 1)return mat[0];//只有一行时直接返回
        vector ans;
        int up = 1;
        for(int i = 0,j = 0;i < m,j < n;){
            ans.push_back(mat[i][j]);
            if(i == m-1 && j == n-1)break;//遍历到最后一个格子证明遍历完成
            if(up){//向上遍历
                if(i - 1 < 0 || j + 1 >= n){//往上遍历时超出边界
                    up = 0;//切换遍历状态并跳转到下一次遍历开始位置
                    if(j + 1 < n)++j;
                    else ++i;
                }
                else {//否则继续往上遍历
                    i--;
                    j++;
                }
            }
            else{
                if(i + 1 >= m || j - 1 < 0){
                    up = 1;
                    if(i+1 < m)i++;
                    else j++;
                }
                else {
                    i++;
                    j--;
                }
            }
        }
        return ans;
    }
};