Problem: 3446. 按對角線進行矩陣排序

思路

發現每條對角線行號減列號是一個定值。
設k=i-j+n，i=0,j=n-1時，k=1；i=m-1，j=0時，k=m+n-1。

解題過程

遍歷對角線，找出最小和最大列，如果最小列大于零說明在矩陣右上角，升序排序，反之逆序排序。

復雜度

• 時間復雜度: $O(n^{2}logn)$
• 空間復雜度: $O(n)$

Code

class Solution {
public:vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();for (int k = 1; k < m + n; k++) {int minj = max(n - k, 0);int maxj = min(m + n - 1 - k, n - 1);vector<int> temp;for (int j = minj; j <= maxj; j++) {temp.push_back(grid[k + j - n][j]);}if (minj > 0) {ranges::sort(temp);} else {ranges::sort(temp, greater<int>());}for (int j = minj; j <= maxj; j++) {grid[k + j - n][j] = temp[j - minj];}}return grid;}
};