日野弥生：勉強しよう
LeetCode 498 - 对角线遍历
发表于2024年12月17日
通过观察发现，矩阵对角线上的两个下标的和是相同的，很自然想到把下标相同的数据存在同一个容器中，还发现：
- 当 i 为偶数时，则第 i 条对角线的走向是从下往上遍历；
- 当 i 为奇数时，则第 i 条对角线的走向是从上往下遍历； 所以需要有一个容器，key为i，value为具体值。
容器个数经过模拟，得出nums.size = m+n-1;
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
int m=mat.size(),n=mat[0].size();
std::vector<std::map<int,int> > nums(m+n-1);
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
nums[i+j].insert({i, mat[i][j]});
}
}
std::vector<int> result{};
for(int i=0;i<nums.size();i++)
{
if(i%2==0)
{
for(auto it=nums[i].rbegin();it!=nums[i].rend();++it)
{
result.push_back(it->second);
}
}
else
{
for(auto it=nums[i].begin();it!=nums[i].end();++it)
{
result.push_back(it->second);
}
}
}
return result;
}
};