1，按对角线进行矩阵排序
题目链接：3446. 按对角线进行矩阵排序 - 力扣（LeetCode）
【题目描述】
对于一个m*n的矩阵grid，要求对该矩阵进行 变换，使得变换后的矩阵满足：
主对角线右上的所有对角线上，元素升序排列。
主对角线左下的所有对角线上，元素降序排列。
【思路】
对于一个矩阵grid，我们可以发现，从右上角到左下角的所有对角线中，同一条对角线上的元素满足：行号i减去列号j是一个定值。
令k=i-j+n，这里加n是为了避免k出现负数。
对于右上角的对角线，k=i-j+n=1。对于左下角的对角线k=m+n-1；
所以，我们可以枚举k=1,2,3,......,m+n-1；相当于从右上角开始，到左下角结束，遍历每条对角线。
接下来需要求出每条对角线上j的取值范围，从而可以遍历对角线上的元素 。
k=i-j+n——>j=i+n-k。
当i=0时，j取最小值，j=n-k。但是j可能会出现负数，所以最小的j=max(0,n-k）。
当i=m-1时，j取最大值，j=m+n-1-k。但是j可能会超出范围，所以最大的j=min(n-1,m+n-1-k）。
对于一个矩阵，如何区别主对角线的右上和左下？？？
我们可以通过j的最小值来确定，观察上图可看出，对于主对角线右上的对角线来说，j的最小值都是大于0的，相反，对于主对角线走下的对角线来说，j的最小值都是等于0的。所以可以 以这点来做区分。
接下来就可以进行模拟了：
枚举k=1,2,3......,m+n-1；
求出每条对角线上j的范围。将该对角线上的 元素加入数组 。排序后（升序或者降序）写回原数组。
【代码】
class Solution {
public:
vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
//k=i-j+n;
int m=grid.size(),n=grid[0].size();
//右上角k=1
//左下角k=m+n-1
for(int k=1;k<m+n;k++)
{
//计算当前对角线的最小值和最大值
int min_j=max(n-k,0);
int max_j=min(m+n-k-1,n-1);
vector<int> a;
for(int j=min_j;j<=max_j;j++)
{
a.push_back(grid[k+j-n][j]);
}
//主对角线右上 升序排列
if(min_j>0)
{
ranges::sort(a);
}
else
{
//主对角线左下 降序排列
ranges::sort(a,greater<int>());
}
//写回数组
for(int j=min_j;j<=max_j;j++)
{
grid[k+j-n][j]=a[j-min_j];
}
}
return grid;
}
};时间复杂度：O(N^2*logN)
空间复杂度：O(N)
2，将矩阵按对角线进行排序
题目链接：1329. 将矩阵按对角线排序 - 力扣（LeetCode）
本题和上题思路一致，但是要求每条对角线都按升序排列。
class Solution {
public:
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
int m=mat.size(),n=mat[0].size();
for(int k=1;k<m+n;k++)
{
int min_j=max(n-k,0);
int max_j=min(m+n-k-1,n-1);
vector<int> a;
for(int j=min_j;j<=max_j;j++)
a.push_back(mat[k+j-n][j]);
ranges::sort(a);
for(int j=min_j;j<=max_j;j++)
mat[k+j-n][j]=a[j-min_j];
}
return mat;
}
};3，对角线上不同值的数量差
题目链接：2711. 对角线上不同值的数量差 - 力扣（LeetCode）
【题目描述】
对于一个大小为m*n的矩阵grid，返回一个同等规模的数组ans，其中ans[i][j]表示：
在矩阵grid中，grid[i][j]左上角对角线中不同值的数量和右下角对角线不同值的数量的差值，对最后结果再取绝对值。
【思路1】暴力计算 ：
遍历grid[i][j]的每一个元素，计算topLeft[i][j]和bottomRight[i][j]。
首先我们可以定义一个unordered_set容器，遍历元素的时候，将元素加入到该容器中。
计算topLeft[i][j]：从[i,j]位置开始，遍历左上角对角线，进行[i--,j--]操作。直到矩阵的边界。
这个过程中，把遍历到的元素加入到容器中，最终topLeft[i][j]就是容器的大小。
计算bottomRight[i][j]：从[i,j]位置开始，遍历右下角对角线，进行[i++,j++]操作。直到矩阵的边界。这个过程中，把遍历到的元素加入到容器中 ，最终bottomRight[i][j]就是容器的大小。
【思路1代码】
class Solution {
public:
vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
vector<vector<int>> ans(m,vector<int>(n,0));
unordered_set<int> st;//天然的去重，容器的大小就是 不同值的数量
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
st.clear();
//查找左上角 不同值的个数
for(int x=i-1,y=j-1;x>=0&&y>=0;x--,y--)
st.insert(grid[x][y]);
int topLeft=st.size();
//查找右下角 不同值的个数
st.clear();
for(int x=i+1,y=j+1;x<m&&y<n;x++,y++)
st.insert(grid[x][y]);
int bottomRight=st.size();
ans[i][j]=abs(topLeft-bottomRight);
}
}
return ans;
}
};时间复杂度：O(m*n*(min(m,n))，m和n分别为grid的行数和列数。
计算一个topLeft和bottomRight需要O(min(m,n))的时间。
【思路2】
该方法就要使用到前面两道题对 对角线的操作思路。
思路一的方法：对于同一条对角线，会遍历多次。比如求ans[0][0]，会遍历一次主对角线，求ans[1][1]的时候，会遍历一次主对角线，求ans[1][1]也会遍历一次主对角线，所以存在多次重复遍历。
我们可以按照前面两道题的思路。
将每条对角线看成是一个一维数组d。
对于d[i]来说：
topLeft[i]是d[i]左侧不同值的数量，我们可以从左向右遍历，将元素加入到哈希集合中，直到遍历到d[i]，此时topLeft就是哈希集合的大小。
bottomRight[i]是右侧不同值的数量 ，我们可以从右向左遍历，将元素加入到哈希集合中，直到遍历到d[i]，此时bottomRight就是哈希集合的大小。
【思路2代码】
class Solution {
public:
vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
unordered_set<int> st;
vector<vector<int>> ans(m,vector<int>(n));
//枚举k 从1到m+n-1
//k=i-j+n
for(int k=1;k<m+n;k++)
{
//求出j的范围
int min_j=max(n-k,0);//i=0时，j=n-k，但不能是负数
int max_j=min(m+n-k-1,n-1);//i=m-1时，j=m+n-1-k,但不能超出范围
st.clear();
//计算左侧不同值的数量 topLeft
//从 左向右遍历
for(int j=min_j;j<=max_j;j++)
{
int i=k+j-n;
ans[i][j]=st.size(); //topLeft[i][j]=st.size();
st.insert(grid[i][j]);
}
//计算右侧最大值的数量 bottomRight
//从右向左遍历
st.clear();
for(int j=max_j;j>=min_j;j--)
{
int i=k+j-n;
ans[i][j]=abs(ans[i][j]-(int)st.size());//st.size()返回值时size_t
st.insert(grid[i][j]);
}
}
return ans;
}
};时间复杂度：O(m*n)，每个单元格访问两次。
4，对角线遍历
题目链接：498. 对角线遍历 - 力扣（LeetCode）
【思路】
我们前面所讲题的对角线遍历，对角线都是从左上角到右下角的一条线。都是主对角线。
而本题 方向相反，都是副对角线。我们可以将数组中的每一行进行翻转，就可以转化成主对角线了。
之后，使用前面的思想，遍历每条对角线。
k=i-j+n；枚举k，从1到m+n-1；
求出每条对角线j的最大值和最小值。
对于每条对角线，我们可能需要从下到上遍历，也可能需要从上到下遍历。对应的j就需要从大到小遍历，也可能需要从小到大遍历。
我们可以定义一个变量flag，flag=1时从下到上遍历，也就是j从从大到小遍历。
flag=0时，从上到下遍历，也就是j从小到大遍历。
开始时，需要从下到上遍历，flag设为1.
【代码】
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
int m=mat.size(),n=mat[0].size();
//翻转每一行
for(auto& v:mat)
{
reverse(v.begin(),v.end());
}
vector<int> ans;
int flag=1;
//k=i-j+n
//1,2,3......m+n-1
//枚举k，枚举每一条对角线
for(int k=1;k<m+n;k++)
{
//求出j的最小值和最大值
int min_j=max(n-k,0);
int max_j=min(m+n-k-1,n-1);
//从下到上遍历 对于j是从大到小遍历
if(flag)
{
for(int j=max_j;j>=min_j;j--)
{
int i=k+j-n;
ans.push_back(mat[i][j]);
}
}
else //从上到下遍历 对应的j从小到大遍历
{
for(int j=min_j;j<=max_j;j++)
{
int i=k+j-n;
ans.push_back(mat[i][j]);
}
}
flag^=1;
}
return ans;
}
};总结：
对角线的遍历（主对角线）：对于一个m*n的矩阵。
在同一条对角线上的元素，行号i减去列号j是一个定值。k=i-j+n；
k的值从1开始到m+n-1。就是主对角线从右上角对角线开始，一直到左下角对角线。
遍历对角线时，我们只需求出j的范围即可，i=k+j-n。但需要注意j不能小于0，也不能超出数组的范围。然后就可以对这条对角线进行操作了。