描述

给定一个大小为 n*m 的矩阵,请以对角线遍历并返回遍历结果
数据范围:  ,矩阵中的元素满足 
例1、输入:[[1,2,3],[4,5,6],[7,8,9]],输出: [1,2,4,7,5,3,6,8,9]
例2、输入:[[1,3],[2,4]],输出:[1,3,2,4]
问题分析:通过观察发现所有(i+j)为奇数的点都是斜向下(除了结尾的点),所有(i+j)为偶数的点(除了开始点)都是斜向上。
奇数点的尾部只要i<m,直接++i,否则++j。而偶数点的开头只要j<n,直接++j,否则++i。
当i=m&&j=n时退出循环。
下面给一个例子:

很直观的可以发现所有奇数点都是斜向下的,而所有偶数点都是斜向上的。()里面表示坐标,
括号外面的数字表示遍历顺序。
复杂度分析:
时间复杂度O(n*m):每个点都只经过一次。
空间复杂度O(n*m):只额外申请了一个容器保存每次遍历的点,这个是必须的。但没有申请复杂空间。
具体过程看如下代码:
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param mat int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> diagonalOrder(vector<vector<int> >& mat) {
        // write code here
        vector<int> res;
        if(mat.size()==0) return res;
        if(mat.size()==1) {//当mat长度为1,说明mat里面只有一个数组
            for(int i=0;i!=mat[0].size();++i) res.push_back(mat[0][i]);
            return res;
        }
        if(mat[0].size()==1) {//当mat[0]长度为1,说明只有1列
            for(int i=0;i!=mat.size();++i) res.push_back(mat[i][0]);
            return res;
        }
        int m=mat.size()-1;
        int n=mat[0].size()-1;
        res.push_back(mat[0][0]);
        int i=0,j=1;
        while(i<=m||j<=n) {//退出循环条件是当i=m&&j=n
            //当i=0或j=n且(i+j)是奇数时,斜向下遍历直到j=0或i=m
            if(((i==0||j==n)&&(i+j)&1)){
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                while(j>0&&i<m) res.push_back(mat[i][j]),++i,--j;
            }
            //当i=0或j=n且(i+j)是偶数时,如果j<n,直接++j;否则++i
            else if((i==0||j==n)&&(i+j)%2==0){
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                if(j<n) res.push_back(mat[i][j]),++j;
                else res.push_back(mat[i][j]),++i;
            }
            //当j=0或i=m且(i+j)是奇数时,如果i<m,++i;否则++j
            if((j==0||i==m)&&(i+j)&1) {
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                if(i<m) res.push_back(mat[i][j]),++i;
                else res.push_back(mat[i][j]),++j;
            } 
            //当j=0或i=m且(i+j)是偶数时,斜向上遍历直到i=0或j=n
            else if((j==0||i==m)&&(i+j)%2==0){
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                while(i>0&&j<n) res.push_back(mat[i][j]),--i,++j;
            }
        }
        return res;
    }
};