题解 | #对角线遍历矩阵#
对角线遍历矩阵
http://www.nowcoder.com/practice/04b591e3537046c68bf398c18b84cb27
描述
给定一个大小为 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;
}
};
