将矩阵按对角线排序 图解题解

对角线各自排成升序，最后返回的是什么

给一个 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))。

两个边界顺手验：单行或单列时每条对角线只剩一格，原样返回；矩阵每条对角线本就升序时，排完不变，也原样返回。

Python

from __future__ import annotations
from 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 = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<int> g[m + n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                g[m - i + j].push_back(mat[i][j]);
            }
        }
        for (auto& e : g) {
            sort(e.rbegin(), e.rend());
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mat[i][j] = g[m - i + j].back();
                g[m - i + j].pop_back();
            }
        }
        return mat;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        List<Integer>[] g = new List[m + n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                g[m - i + j].add(mat[i][j]);
            }
        }
        for (List<Integer> e : g) {
            Collections.sort(e, (a, b) -> b - a);
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mat[i][j] = g[m - i + j].remove(g[m - i + j].size() - 1);
            }
        }
        return mat;
    }
}