题目描述
思路解析
一句话答案：LeetCode 1329 将矩阵按对角线排序：同一条右下对角线上 i-j 是常数，就按 i-j 把数分组、组内升序再原位写回，时间 O(m·n·log(min(m,n)))。
对角线各自排成升序，最后返回的是什么
给一个 m 行 n 列的矩阵 mat，它的对角线是沿右下方向的斜线，从最上一行或最左一列的某格出发一路走到底。题目要把每条对角线单独拎出来，线上的数从小到大排成升序，其余位置不动，返回整个矩阵。题面 mat=[[3,3,1,1],[2,2,1,2],[1,1,1,2]] 处理完是 [[1,1,1,1],[1,2,2,2],[1,2,3,3]]。
同一条对角线上的格子，凭什么一眼认出来
认对角线是这题的门槛：怎么知道 (0,0) 和 (1,1)、(2,2) 是一伙的？沿右下走一步，行号加一、列号也加一，i-j 一减一加正好不变。所以同一条右下对角线上的格子 i-j 全相等——主对角线三格的 i-j 都是 0，右上那条 (0,1)、(1,2)、(2,3) 都是 -1。而 i+j 相等的是右上的反对角线，方向拧着，别认错。格子归哪条线，减一下 i-j 就知道。
按 i-j 分组、排序、写回，负下标怎么办
剩下是三步：先按 i-j 把每个数扔进对应的桶，再把每个桶单独升序排好，最后沿右下从上往下写回，最小的落最左上的格子。有个小坑，i 小 j 大时 i-j 是负的，直接当数组下标会越界。办法是偏移一个常数，比如 i-j+n 或参考代码里的 m-i+j，把编号压进 0 到 m+n-1 这段非负区间；或者用哈希表按 i-j 归桶，键是负数也无妨。
参考代码明明排的是降序，怎么写回却成了升序
参考代码有个反直觉处：每个桶排的是降序（e.sort(reverse=True)），矩阵却成了升序。诀窍在写回用的是 pop()——从桶尾弹数，降序数组的末尾恰好是最小值。写回按行列顺序遍历，同一条对角线总先碰到最左上的格子，弹出的又是当前最小的数，于是一路填下来就是升序，省了一次反转。
主对角线先走一趟，看 3×4 矩阵怎么排
盯住 i-j 等于 0 这条主对角线，三格原始值 mat[0][0]=3、mat[1][1]=2、mat[2][2]=1，沿右下收集得 3、2、1，升序排好是 1、2、3。再从上往下写回：第 1 小的 1 填进 (0,0)，第 2 小的 2 填进 (1,1)，最大的 3 填进 (2,2)。
别的对角线同理：i-j 等于 -1 那条 (0,1)、(1,2)、(2,3) 收到 3、1、2，排成 1、2、3；四个角上只有一格的短对角线本身就升序，不动。六条线处理完，就是开头那个升序矩阵。
方向一记反，右上那组斜线就被你排了
最容易栽的是方向：判据记成 i+j 相等，排的就成了右上那组斜线，答案整片错位。其次是负下标，i-j 为负时不偏移就越界。还有写回方向，得沿右下从上往下把最小值放左上；从右下往左上写、或降序填回，对角线就反了。
复杂度上，收集和写回各扫一遍是 O(m·n)，开销主要在排序：所有对角线共 m·n 个数分段排，总量 O(m·n·log(min(m,n)))。空间上参考代码用桶存全部元素占 O(m·n)，逐条处理可压到 O(min(m,n))。
两个边界顺手验：单行或单列时每条对角线只剩一格，原样返回；矩阵每条对角线本就升序时，排完不变，也原样返回。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
三步走:按 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题