3446. 按对角线进行矩阵排序

🎯 问题描述

描述：
给你一个大小为 n x m 的整数矩阵 grid。
请你返回一个经过调整的矩阵，调整规则如下：

左下角三角形（包括主对角线）：该区域内的每一条对角线（从左上到右下方向）按非递增（降序）顺序排序。
右上角三角形：该区域内的每一条对角线按非递减（升序）顺序排序。

说明：

这是一个坐标变换结合分组排序的问题。
核心策略：
- 利用数学公式将二维坐标映射到一维对角线索引。
- 通过枚举对角线标识符 k 来遍历所有副对角线。
- 提取对角线元素 -> 排序 -> 写回矩阵。
排序规则：根据对角线起始位置动态决定排序方向。
示例：
示例 1：

输入：grid = 
输出：
解释：
- 主对角线 [1,8,6] (i-j=0)：属于左下角区域（含主对角线），降序排序 -> [8,6,1]。
- 对角线 [9,5] (i-j=1)：属于左下角，降序 -> [9,5] (不变)。
- 对角线 [4] (i-j=2)：属于左下角，降序 -> [4] (不变)。
- 对角线 [7,2] (i-j=-1)：属于右上角，升序 -> [2,7]。
- 对角线 [3] (i-j=-2)：属于右上角，升序 -> [3] (不变)。

💻 解题思路

思路1：坐标映射 + 数学边界推导

核心逻辑

枚举副对角线：
- 副对角线（右上到左下方向）的特征是坐标满足线性关系 i - j = k - m。
- 通过变量 k (范围 1 到 m+n-1) 来枚举所有可能的副对角线。
精确计算边界：
- min_j = max(0, n - k)：确保行下标 i 在有效范围内。
- max_j = min(m - 1, n - 1 + m - k)：确保列下标 j 在有效范围内。
动态排序规则：
- a.sort(reverse = min_j == 0)：
  - 当 min_j == 0 时，对角线从第一行开始，执行降序排序。
  - 当 min_j > 0 时，对角线从第一列开始，执行升序排序。
原地写回：
- 利用 zip 将排序后的值和对应的列下标配对，直接写回 grid。
- 行下标通过公式 k + j - m 还原。

代码实现

class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        n, m = len(grid), len(grid[0])
        
        # 枚举每一条副对角线
        for k in range(1, m + n):
            # 计算当前对角线在列方向上的有效范围 [min_j, max_j]
            min_j = max(0, n - k)
            max_j = min(m - 1, n - 1 + m - k)
            
            # 提取当前对角线上的元素
            # 行坐标 i = k - m + j
            a = [grid[k - m + j][j] for j in range(min_j, max_j + 1)]
            
            # 根据起始位置决定排序方向
            # 如果 min_j == 0，说明对角线从第一行开始（右上部分），降序
            # 否则，从第一列开始（左下部分），升序
            a.sort(reverse=(min_j == 0))
            
            # 将排序后的元素写回矩阵
            for j, val in zip(range(min_j, max_j + 1), a):
                grid[k + j - m][j] = val
                
        return grid

📊 性能分析

时间复杂度： $O((N+M) \cdot K \log K)$ $O ((N + M) \cdot K lo g K)$
- 其中 $K$ 是对角线的平均长度。
- 需要遍历 $N+M-1$ 条对角线。
- 每条对角线的排序耗时 $O(L \log L)$ ，其中 $L$ 是该对角线的长度。
- 总体复杂度为 $O(NM \log(\min(N, M)))$ 。
空间复杂度： $O(\min(N, M))$ $O (min (N, M))$
- 需要一个临时数组 a 来存储对角线元素，其最大长度为矩阵的最短边。

思考

坐标变换的数学原理：
- 副对角线的特点是行标与列标之差为定值。
- 代码中使用了 i = k - m + j，变换后得 i - j = k - m。
- 令 $C = k - m$ ，则 i - j = C。随着 k 的变化，我们遍历了所有可能的 i-j 差值，从而覆盖了所有副对角线。
边界计算的推导：
- 需要保证计算出的行 i 和列 j 都在矩阵范围内。
- 由 0 <= i < n 和 i = k - m + j，可得 0 <= k - m + j < n。
- 移项得 m - k <= j < n + m - k。
- 结合 0 <= j < m，取交集即可得到 min_j 和 max_j 的公式。
排序方向的逻辑：
- 代码中的 reverse=(min_j == 0) 是一个非常巧妙的写法。
- 当 min_j == 0 时，意味着列坐标可以从 0 开始，这通常对应于从第一行出发的对角线（右上部分）。
- 当 min_j > 0 时，意味着列坐标必须大于 0，这通常对应于从第一列出发的对角线（左下部分）。
代码的健壮性：
- 使用 zip 进行写回操作非常 Pythonic，避免了手动维护索引。
- 边界计算使用了 max 和 min 函数，确保了索引不会越界。
- 原地修改避免了额外的存储空间开销。