Medium

题目描述

给你一个 n x n 的整数方阵 grid。请你返回满足以下条件的矩阵：

  • 左下三角形（包括中间对角线）的对角线按非递增顺序排序。
  • 右上三角形的对角线按非递减顺序排序。

示例 1：

输入：grid = [[1,7,3],[9,8,2],[4,5,6]]
输出：[[8,2,3],[9,6,7],[4,5,1]]
解释：

带黑色箭头的对角线（左下三角形）应按非递增顺序排序：
- [1, 8, 6] 变为 [8, 6, 1]。
- [9, 5] 和 [4] 保持不变。

带蓝色箭头的对角线（右上三角形）应按非递减顺序排序：
- [7, 2] 变为 [2, 7]。
- [3] 保持不变。

示例 2：

输入：grid = [[0,1],[1,2]]
输出：[[2,1],[1,0]]
解释：

带黑色箭头的对角线必须非递增，所以 [0, 2] 变为 [2, 0]。其他对角线已经是正确的顺序。

示例 3：

输入：grid = [[1]]
输出：[[1]]
解释：

只有一个元素的对角线已经有序，所以不需要改变。

约束条件：

  • grid.length == grid[i].length == n
  • 1 <= n <= 10
  • -10^5 <= grid[i][j] <= 10^5

提示：

  • 使用数据结构存储每条对角线中的所有值。
  • 排序后在矩阵中替换它们。

解题思路

解题思路

这道题的关键是理解对角线的概念和如何识别左下三角形和右上三角形的对角线。

对角线的识别方法

在二维矩阵中，我们可以通过以下特征来识别对角线：

  • 主对角线方向：从左上到右下，特征是 i - j 为常数
  • 反对角线方向：从右上到左下，特征是 i + j 为常数

对于这道题，我们需要按主对角线方向进行排序。

左下三角形 vs 右上三角形

  • 左下三角形（包括主对角线）：i >= j 的位置，这些对角线需要非递增排序
  • 右上三角形：i < j 的位置，这些对角线需要非递减排序

算法步骤

  1. 遍历所有可能的对角线（通过 i - j 的值确定）
  2. 对每条对角线，收集所有元素
  3. 根据对角线所在的三角形区域选择排序方式：
    • 左下三角形：降序排序（非递增）
    • 右上三角形：升序排序（非递减）
  4. 将排序后的元素重新放回矩阵对应位置

时间复杂度主要由排序操作决定，由于矩阵大小限制在 10x10，性能不是问题。

代码实现

class Solution {
public:
    vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        
        // 处理每条对角线
        for (int diff = -(n-1); diff <= n-1; diff++) {
            vector<int> diagonal;
            vector<pair<int, int>> positions;
            
            // 收集当前对角线的元素和位置
            for (int i = 0; i < n; i++) {
                int j = i - diff;
                if (j >= 0 && j < n) {
                    diagonal.push_back(grid[i][j]);
                    positions.push_back({i, j});
                }
            }
            
            // 确定排序方式
            if (diff <= 0) {
                // 左下三角形（包括主对角线），非递增排序
                sort(diagonal.rbegin(), diagonal.rend());
            } else {
                // 右上三角形，非递减排序
                sort(diagonal.begin(), diagonal.end());
            }
            
            // 将排序后的元素放回原位置
            for (int k = 0; k < positions.size(); k++) {
                grid[positions[k].first][positions[k].second] = diagonal[k];
            }
        }
        
        return grid;
    }
};

class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        
        # 处理每条对角线
        for diff in range(-(n-1), n):
            diagonal = []
            positions = []
            
            # 收集当前对角线的元素和位置
            for i in range(n):
                j = i - diff
                if 0 <= j < n:
                    diagonal.append(grid[i][j])
                    positions.append((i, j))
            
            # 确定排序方式
            if diff <= 0:
                # 左下三角形（包括主对角线），非递增排序
                diagonal.sort(reverse=True)
            else:
                # 右上三角形，非递减排序
                diagonal.sort()
            
            # 将排序后的元素放回原位置
            for k, (i, j) in enumerate(positions):
                grid[i][j] = diagonal[k]
        
        return grid

public class Solution {
    public int[][] SortMatrix(int[][] grid) {
        int n = grid.Length;
        
        // 处理每条对角线
        for (int diff = -(n-1); diff <= n-1; diff++) {
            List<int> diagonal = new List<int>();
            List<(int, int)> positions = new List<(int, int)>();
            
            // 收集当前对角线的元素和位置
            for (int i = 0; i < n; i++) {
                int j = i - diff;
                if (j >= 0 && j < n) {
                    diagonal.Add(grid[i][j]);
                    positions.Add((i, j));
                }
            }
            
            // 确定排序方式
            if (diff <= 0) {
                // 左下三角形（包括主对角线），非递增排序
                diagonal.Sort((a, b) => b.CompareTo(a));
            } else {
                // 右上三角形，非递减排序
                diagonal.Sort();
            }
            
            // 将排序后的元素放回原位置
            for (int k = 0; k < positions.Count; k++) {
                grid[positions[k].Item1][positions[k].Item2] = diagonal[k];
            }
        }
        
        return grid;
    }
}

var sortMatrix = function(grid) {
    const n = grid.length;
    
    // 处理每条对角线
    for (let diff = -(n-1); diff <= n-1; diff++) {
        const diagonal = [];
        const positions = [];
        
        // 收集当前对角线的元素和位置
        for (let i = 0; i < n; i++) {
            const j = i - diff;
            if (j >= 0 && j < n) {
                diagonal.push(grid[i][j]);
                positions.push([i, j]);
            }
        }
        
        // 确定排序方式
        if (diff <= 0) {
            // 左下三角形（包括主对角线），非递增排序
            diagonal.sort((a, b) => b - a);
        } else {
            // 右上三角形，非递减排序
            diagonal.sort((a, b) => a - b);
        }
        
        // 将排序后的元素放回原位置
        for (let k = 0; k < positions.length; k++) {
            grid[positions[k][0]][positions[k][1]] = diagonal[k];
        }
    }
    
    return grid;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n² log n)
空间复杂度O(n)

时间复杂度分析：

  • 有 2n-1 条对角线需要处理
  • 每条对角线最多有 n 个元素需要排序，排序复杂度为 O(n log n)
  • 总时间复杂度为 O(n × n log n) = O(n² log n)

空间复杂度分析：

  • 需要额外的数组存储每条对角线的元素，最大长度为 n
  • 位置数组也最多存储 n 个位置信息
  • 总空间复杂度为 O(n)

相关题目