题解 | #对角线遍历矩阵#
对角线遍历矩阵
https://www.nowcoder.com/practice/04b591e3537046c68bf398c18b84cb27
思路：
我们可以先手动画一下，发现Z形走法在遇到边界的时候有2个方向——从右上往坐下走，此时x++,y--；从坐下往右上走，此时x--,y++。因此我们可以定义2个方向{dx=1,dy=-1}和{dx=-1,dy=1}。
另外，在走某一条路的时候，x+y的和是不变的，只有在(x,y)所代表的坐标到达4个边框的时候，才将x或者y加一，至于需要将x还是y加一，需要根据四种情况进行分析。
1. 如果在上边界，也就是x=0的时候，且y < n - 1，则y递增
2. 如果在左边界，也就是y=0的时候，且x < m - 1，则x递增
3. 如果在右边界，也就是y=n-1的时候，且x < m - 1，则x递增
4. 如果在下边界，也就是x = m - 1的时候，且y < n - 1，则y递增
我们可以先手动画一下，发现Z形走法在遇到边界的时候有2个方向——从右上往坐下走，此时x++,y--；从坐下往右上走，此时x--,y++。因此我们可以定义2个方向{dx=1,dy=-1}和{dx=-1,dy=1}。
另外，在走某一条路的时候，x+y的和是不变的，只有在(x,y)所代表的坐标到达4个边框的时候，才将x或者y加一，至于需要将x还是y加一，需要根据四种情况进行分析。
1. 如果在上边界，也就是x=0的时候，且y < n - 1，则y递增
2. 如果在左边界，也就是y=0的时候，且x < m - 1，则x递增
3. 如果在右边界，也就是y=n-1的时候，且x < m - 1，则x递增
4. 如果在下边界，也就是x = m - 1的时候，且y < n - 1，则y递增
注意：
1. 可以不在堆上分配的内存，尽量不要在堆上分配
2. 这里ans的大小实际上是直到的，因此一开始我们就可以分配好需要的内存
以上2个优化，代码直接从超过0%变成了超过100%~~
代码如下：
#include <bits/stdc++.h>
using namespace std;
vector<int> diagonalOrder(vector<vector<int>> &mat)
{
std::vector<int> ans;
int x = 0;
int y = 0;
int m = mat.size();
int n = mat[0].size();
ans.reserve(m * n);
std::pair<int, int> direct[2] = {{-1, 1}, {1, -1}}; // 2个方向：从左下角往右上角走，从右上角往左下角走
int d = 0; // 初始方向其实无所谓，主要是d=1的时候要从右上角往左下角走
while (true)
{
auto dx = direct[d % 2].first;
auto dy = direct[d % 2].second;
d++; // 更新下一次的方向
// 嗯，这里其实可以使用do{}while(conditian)来实现~~
ans.push_back(mat[x][y]); // 将当前坐标放入遍历结果
while ((dx + x >= 0 && dx + x <= m - 1) && (dy + y >= 0 && dy + y <= n - 1)) // 往2个方向走
{
x = dx + x;
y = dy + y;
ans.push_back(mat[x][y]);
}
if (x == m - 1 && y == n - 1) // 已经到达最后一个位置
{
break;
}
// 处理四个边界问题，具体意思看代码自己理解吧~~
if (x == 0 && y < n - 1)
{
x = 0; // 这里的x=0起始是可以不写的，哈，只是为了看着方便点~~
y++;
}
else if (y == 0 && x < m - 1)
{
y = 0;
x += 1;
}
else if (y == n - 1 && x < m - 1)
{
y = n - 1;
x += 1;
}
else if (x == m - 1)
{
y++;
x = m - 1;
}
}
return ans;
}
