LeetCode 3446. 按对角线进行矩阵排序 - 从复杂到简洁的优化思考
题目描述
给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：
- 左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序
- 右上角三角形 的对角线按 非递减顺序 排序
示例
示例 1：
输入： grid = [[1,7,3],[9,8,2],[4,5,6]]
输出： [[8,2,3],[9,6,7],[4,5,1]]
示例 2：
输入： grid = [[0,1],[1,2]]
输出： [[2,1],[1,0]]
解题思路的演进
第一版：收集-排序-放回
最初的想法是传统的排序方法：
def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
n = len(grid)
if n <= 1:
return grid
# 处理左下角三角形 - 非递增排序
for i in range(n):
r, c = i, 0
diagonal_length = min(n - i, n)
# 收集当前对角线的元素
diagonal = []
for j in range(diagonal_length):
diagonal.append(grid[r + j][c + j])
# 对对角线元素进行非递增排序
diagonal.sort(reverse=True)
# 将排序后的元素放回原位置
for j in range(diagonal_length):
grid[r + j][c + j] = diagonal[j]
# 处理右上角三角形 - 非递减排序
for j in range(1, n):
r, c = 0, j
diagonal_length = min(n, n - j)
# 收集当前对角线的元素
diagonal = []
for l in range(diagonal_length):
diagonal.append(grid[r + l][c + l])
# 对对角线元素进行非递减排序
diagonal.sort()
# 将排序后的元素放回原位置
for l in range(diagonal_length):
grid[r + l][c + l] = diagonal[l]
return grid
问题： 需要额外的内存空间存储对角线元素，时间复杂度 O(n² log n)
第二版：插入排序优化
为了减少内存分配，改用插入排序：
def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
n = len(grid)
if n <= 1:
return grid
# 处理左下角三角形 - 非递增排序
for i in range(n):
r, c = i, 0
diagonal_length = min(n - i, n)
# 使用插入排序进行非递增排序（降序）
for j in range(1, diagonal_length):
key = grid[r + j][c + j]
k = j - 1
# 将大于key的元素向后移动
while k >= 0 and grid[r + k][c + k] < key:
grid[r + k + 1][c + k + 1] = grid[r + k][c + k]
k -= 1
grid[r + k + 1][c + k + 1] = key
# 处理右上角三角形 - 非递减排序
for j in range(1, n):
r, c = 0, j
diagonal_length = min(n, n - j)
# 使用插入排序进行非递减排序（升序）
for l in range(1, diagonal_length):
key = grid[r + l][c + l]
k = l - 1
# 将大于key的元素向后移动
while k >= 0 and grid[r + k][c + k] > key:
grid[r + k + 1][c + k + 1] = grid[r + k][c + k]
k -= 1
grid[r + k + 1][c + k + 1] = key
return grid
优化点： 空间复杂度降为 O(1)，但时间复杂度变为 O(n³)
第三版：误解与纠正
在优化过程中，我产生了一个误解：
错误想法： 如果只需要"非递增"和"非递减"，那么只需要一次交换就能破坏严格递增/递减性质
# 错误版本 - 只交换一次
for j in range(diagonal_length - 1):
if grid[r + j][c + j] < grid[r + j + 1][c + j + 1]:
grid[r + j][c + j], grid[r + j + 1][c + j + 1] = grid[r + j + 1][c + j + 1], grid[r + j][c + j]
break # 只需要交换一次
问题分析：
- 对于 [1,8,6]，交换一次变成 [8,1,6]，虽然破坏了递增，但不是完全降序
- 题目要求的是完整的排序，不是仅仅破坏递增/递减性质
最终版：简洁高效的实现
经过多次思考和验证，最终确定了正确的算法：
from typing import List
class Solution:
def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
n = len(grid)
if n <= 1:
return grid
# 左下角三角形 - 非递增排序（降序）
for i in range(n):
r, c = i, 0
l = min(n - i, n)
# 收集对角线元素
d = []
for j in range(l):
d.append(grid[r + j][c + j])
# 降序排序
d.sort(reverse=True)
# 放回
for j in range(l):
grid[r + j][c + j] = d[j]
# 右上角三角形 - 非递减排序（升序）
for j in range(1, n):
r, c = 0, j
l = min(n, n - j)
# 收集对角线元素
d = []
for k in range(l):
d.append(grid[r + k][c + k])
# 升序排序
d.sort()
# 放回
for k in range(l):
grid[r + k][c + k] = d[k]
return grid
关键理解点
1. "非递增"和"非递减"的真正含义
- 非递增顺序 = 降序排列，可以包含相等元素
- 非递减顺序 = 升序排列，可以包含相等元素
2. 为什么不能只用一次交换？
错误理解： 一次交换就能破坏严格递增/递减性质
正确理解： 需要完整的排序才能满足题目要求
举例说明：
- 输入：[1,8,6]
- 错误做法：交换一次 → [8,1,6] ❌
- 正确做法：完整排序 → [8,6,1] ✅
3. 算法复杂度分析
| 版本 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 第一版 | O(n² log n) | O(n) | 传统方法，内存开销大 |
| 第二版 | O(n³) | O(1) | 插入排序，原地操作 |
| 最终版 | O(n² log n) | O(n) | 平衡了效率和简洁性 |
总结
这道题目教会了我几个重要的编程思维：
- 仔细理解题目要求：不能想当然地简化问题
- 验证算法正确性：通过具体例子验证思路
- 权衡效率与简洁：在时间复杂度和代码可读性之间找到平衡
- 持续优化：从复杂到简单，不断改进算法
最终，虽然我回到了"收集-排序-放回"的基本思路，但通过这个过程，我更深刻地理解了算法的本质和优化的边界。
标签： #LeetCode #算法优化 #矩阵排序 #对角线排序 #Python
更新日期2025年8月28日