LeetCode Diagonal Traverse Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image. Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:

Note:

1. The total number of elements of the given matrix will not exceed 10,000.

---

给定一个矩阵，要求以对角线的方式遍历该矩阵。 没什么特别的技巧，模拟对角线走法即可。设置一个up变量，设置up=true表示向右上角走，i–,j++；up=false表示向左下角走，i++,j–。 边界情况处理有点复杂。当向右上角走时，有两种情况，如果越过了右边界，比如样例中3往右上角走了一步，则要回到6的位置，方法是i+=2,j=n-1；如果没有越过右边界，只是越过了上边界，比如图中的1再往右上角走了一步，则只需要i=0。注意这两种判断的顺序不能乱，必须先判断是否越过了右边界，再判断是否越过了上边界。 当往左下角走时，越界处理的方法类似。如果越过了下边界，比如8再往左下角走了一步，则需要i=m-1,j+=2；如果只越过了左边界，比如4再往左下角走了一步，则只需要j=0。 完整代码如下： [cpp] class Solution { public: vector<int> findDiagonalOrder(vector<vector<int>>& matrix) { int m = matrix.size(), n = 0; if (m != 0)n = matrix[0].size(); if (m == 0 || n == 0)return vector<int>(); vector<int> ans; int i = 0, j = 0; bool up = true; while (!(i == m – 1 && j == n – 1)) { ans.push_back(matrix[i][j]); if (up) { –i; ++j; if (j >= n) { i += 2; j = n – 1; up = false; } if (i < 0) { i = 0; up = false; } } else { ++i; –j; if (i >= m) { i = m – 1; j += 2; up = true; } if (j < 0) { j = 0; up = true; } } } ans.push_back(matrix[m – 1][n – 1]); return ans; } }; [/cpp] 本代码提交AC，用时86MS。]]>