题目描述
思路解析动画文字版
三步走:按 i-j 把格子分到各条对角线,每条单独升序,再沿右下从上往下把数从小到大写回。i-j 可能为负,记得偏移成非负下标。
总览 · 原始 3×4 矩阵：这是要处理的 3 行 4 列矩阵,行号 i 从上到下 0、1、2,列号 j 从左到右 0 到 3。接下来一条一条对角线来处理:每条线先整体点亮、收集线上的数,再升序排好,然后从最上面那格起把数从小到大写回。处理完的格子会标成蓝色定稿,正在处理的标橙色。先看主对角线。
对角线 i-j=0 · 收集：点亮的是 i-j 等于 0 这条对角线,经过 (0,0)、(1,1)、(2,2)。沿右下从上往下把数收集起来,得到 3、2、1。右边面板就是这条线现在的原始排列,还没排序。
对角线 i-j=0 · 排序：把刚收集的 3、2、1 单独升序排一下,得到 1、2、3。注意只在这条对角线内部排,不和别的对角线混。排好后就该把它们从上往下写回去,最小的写在最靠左上的那格。
对角线 i-j=0 · 写回 (0,0)：把这条线第 1 小的数 1 写进格子 (0,0)。它是从上往下第 1 个位置,正好放第 1 小的数。右边面板里还剩 2、3,等着填进更靠右下的格子。
对角线 i-j=0 · 写回 (1,1)：把这条线第 2 小的数 2 写进格子 (1,1)。它是从上往下第 2 个位置,正好放第 2 小的数。右边面板里还剩 3,等着填进更靠右下的格子。
对角线 i-j=0 · 写回 (2,2)：把这条线最大的数 3 写进格子 (2,2)。它是从上往下第 3 个位置,正好放第 3 小的数。这条对角线已经全部就位。
对角线 i-j=-1 · 收集：点亮的是 i-j 等于 -1 这条对角线,经过 (0,1)、(1,2)、(2,3)。沿右下从上往下把数收集起来,得到 3、1、2。右边面板就是这条线现在的原始排列,还没排序。
对角线 i-j=-1 · 排序：把刚收集的 3、1、2 单独升序排一下,得到 1、2、3。注意只在这条对角线内部排,不和别的对角线混。排好后就该把它们从上往下写回去,最小的写在最靠左上的那格。
对角线 i-j=-1 · 写回 (0,1)：把这条线第 1 小的数 1 写进格子 (0,1)。它是从上往下第 1 个位置,正好放第 1 小的数。右边面板里还剩 2、3,等着填进更靠右下的格子。
对角线 i-j=-1 · 写回 (1,2)：把这条线第 2 小的数 2 写进格子 (1,2)。它是从上往下第 2 个位置,正好放第 2 小的数。右边面板里还剩 3,等着填进更靠右下的格子。
对角线 i-j=-1 · 写回 (2,3)：把这条线最大的数 3 写进格子 (2,3)。它是从上往下第 3 个位置,正好放第 3 小的数。这条对角线已经全部就位。
对角线 i-j=-2 · 收集：点亮的是 i-j 等于 -2 这条对角线,经过 (0,2)、(1,3)。沿右下从上往下把数收集起来,得到 1、2。右边面板就是这条线现在的原始排列,还没排序。
对角线 i-j=-2 · 排序：把刚收集的 1、2 单独升序排一下,得到 1、2。注意只在这条对角线内部排,不和别的对角线混。排好后就该把它们从上往下写回去,最小的写在最靠左上的那格。
对角线 i-j=-2 · 写回 (0,2)：把这条线第 1 小的数 1 写进格子 (0,2)。它是从上往下第 1 个位置,正好放第 1 小的数。右边面板里还剩 2,等着填进更靠右下的格子。
对角线 i-j=-2 · 写回 (1,3)：把这条线最大的数 2 写进格子 (1,3)。它是从上往下第 2 个位置,正好放第 2 小的数。这条对角线已经全部就位。
对角线 i-j=-3 · 单元素：这条对角线只有一个格子 (0,3),值是 1。单个元素本身就是升序,不用排也不用动,直接定稿。
对角线 i-j=1 · 收集：点亮的是 i-j 等于 1 这条对角线,经过 (1,0)、(2,1)。沿右下从上往下把数收集起来,得到 2、1。右边面板就是这条线现在的原始排列,还没排序。
对角线 i-j=1 · 排序：把刚收集的 2、1 单独升序排一下,得到 1、2。注意只在这条对角线内部排,不和别的对角线混。排好后就该把它们从上往下写回去,最小的写在最靠左上的那格。
对角线 i-j=1 · 写回 (1,0)：把这条线第 1 小的数 1 写进格子 (1,0)。它是从上往下第 1 个位置,正好放第 1 小的数。右边面板里还剩 2,等着填进更靠右下的格子。
对角线 i-j=1 · 写回 (2,1)：把这条线最大的数 2 写进格子 (2,1)。它是从上往下第 2 个位置,正好放第 2 小的数。这条对角线已经全部就位。
对角线 i-j=2 · 单元素：这条对角线只有一个格子 (2,0),值是 1。单个元素本身就是升序,不用排也不用动,直接定稿。
回放 · 排好的矩阵：六条对角线全部处理完。现在每一条从左上到右下的对角线都是升序的:主对角线是 1、2、3,它上面那条是 1、2、3,顶上和最左边那些短对角线也都各自升序。拼起来就是答案,第一行 1、1、1、1,第二行 1、2、2、2,第三行 1、2、3、3。整个过程就是分组、排序、写回这三步反复做。
边界都好验:单行或单列时每条对角线只有一格、原样返回;某矩阵每条对角线本就升序时也原样返回。
面试三连:i-j 不变是因为右下走行列同增;降序桶从尾弹出最小值、按行列顺序写回就成升序;按对角线分段排序总量 O(m·n·log(min(m,n)))。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]: m, n = len(mat), len(mat[0]) g = [[] for _ in range(m + n)] for i, row in enumerate(mat): for j, x in enumerate(row): g[m - i + j].append(x) for e in g: e.sort(reverse=True) for i in range(m): for j in range(n): mat[i][j] = g[m - i + j].pop() return mat复杂度
- 时间：O(m·n·log(min(m,n)))，每个格子被收集和写回各一次,是 O(m·n);真正的开销在排序,每条对角线最长 min(m,n) 个数,所有对角线加起来共 m·n 个数、按对角线分段排序,总排序量是 O(m·n·log(min(m,n)))
- 空间：O(m·n)，按峰值算:参考代码把全部 m·n 个数都分散存进了各个桶,额外占 O(m·n)。若改成一条对角线处理完再处理下一条,辅助空间可压到一条线的长度 O(min(m,n))。排序自身的栈开销被桶占用量覆盖
易错点
面试追问把动画讲成自己的话
追问为什么同一条右下对角线上的 i-j 是个常数?
追问参考代码明明排的是降序,怎么最后矩阵是升序的?
追问这题和直接对整个矩阵排序有什么本质区别?复杂度怎么算?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二进制字符串前缀一致的次数
LeetCode 1375 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题