498. Diagonal Traverse ----------M

 

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:

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

A:

就是个实现题。 考的是细心不出错。

思路是这样的，每次斜着走，从右上，往左下走。然后，加入到结果里

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int m = matrix.size();
        if(m==0)
            return res;
        int n = matrix[0].size();
        int r =0, c = 0;
        for(int r = 0, c = 0; r<m && c<n; c==n-1?r++:c++){
            vector<int> V;
            // go to the down-left direction
            int rr = r, cc = c;
            while(rr<m && cc>=0){
                if( (rr+cc)%2 == 1){
                    V.push_back(matrix[rr][cc]);
                }else{
                    V.insert(V.begin(), matrix[rr][cc]);
                }
                rr++;
                cc--;
            }
            res.insert(res.end(), V.begin(), V.end());
        }
        return res;
    }
};