[LeetCode]Diagonal Traverse

按照题目的要求，模仿对角线遍历即可。也就是说，假设m行n列，[i][j]表示第i + 1行j + 1列，对于以下几种情况：

1. 如果i < 0, i = 0, 换方向
2. 如果j < 0, j = 0, 换方向
3. 如果i >= m, --i, j += 2, 换方向
4. 如果j >= n, --j, i += 2，换方向

O(n)时间，常数空间，代码如下：

	class Solution {
	public:
	vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
	int m = matrix.size(), n = m? matrix[0].size(): 0, count = 0, d = 0, i = 0, j = 0;
	vector<pair<int, int>> dirs = {{-1, 1}, {1, -1}};
	vector<int> res;
	while(count < m * n)
	{
	res.push_back(matrix[i][j]);
	auto p = dirs[d];
	i += p.first;
	j += p.second;
	++count;
	if(j >= n){--j; i += 2; d = 1 - d;}
	if(i >= m){--i; j += 2; d = 1 - d;}
	if(i < 0) {i = 0; d = 1 - d;}
	if(j < 0) {j = 0;d = 1 - d;}
	}
	return res;
	}
	};

view raw Diagonal Traverse.cpp hosted with ❤ by GitHub