你好，同学。很高兴看到你在钻研矩阵处理类的题目。这道题虽然在 LeetCode 上标为中等，但在 NOI 普及组（入门级）或提高组的初级阶段，是非常经典的“下标变换与模拟”练习题。

作为你的教练，我不会直接给你代码，但我会引导你如何从观察规律开始，一步步在草稿纸上把这道题“解构”。

一、 预备知识点

1. 二维数组遍历：理解 $(i, j)$ 坐标体系。
2. 对角线数学性质：掌握矩阵中“左上到右下”对角线的下标特征。
3. 排序算法的应用：能够灵活使用标准库 std::sort。
4. STL 容器的使用：如 std::vector 或动态数组，用于临时存储对角线元素。

二、 题目描述 (NOI 竞赛风格)

题目名称：将矩阵按对角线排序 (Sort the Matrix Diagonally)

【问题描述】 给定一个 $m \times n$ 的整数矩阵 $A$。矩阵的“矩阵对角线”定义为从某一行最左侧或某一行最上端开始，向右下方延伸直至到达矩阵边界的所有元素组成的序列。 例如，如果矩阵为 $3 \times 4$，则从 $A[1][0]$ 开始的对角线包含元素 $A[1][0], A[2][1]$。 你的任务是将矩阵中每一条对角线上的元素按升序进行排序，并输出排序后的矩阵。

【输入格式】 第一行包含两个正整数 $m$ 和 $n$，表示矩阵的行数和列数。 接下来 $m$ 行，每行包含 $n$ 个以空格分隔的整数，表示矩阵 $A$ 的元素。

【输出格式】 输出 $m$ 行，每行包含 $n$ 个整数，表示按要求排序后的矩阵。

【样例 1 输入】

3 4
3 3 1 1
2 2 1 2
1 1 1 2

【样例 1 输出】

1 1 1 1
1 2 2 2
1 2 3 3

【数据规模与约定】

• $1 \le m, n \le 100$
• $1 \le A[i][j] \le 100$

三、 启发式引导：草稿纸上的推理过程

现在，请拿出你的草稿纸，跟我一起画图分析：

第一步：观察对角线下标规律

我们在纸上画一个 $3 \times 4$ 的矩阵，写下每个位置的坐标 $(i, j)$：

(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)

思考： 同一条对角线上的元素，它们的行下标 $i$ 和列下标 $j$ 有什么共同点？

• 对角线1：(0,0), (1,1), (2,2) $\rightarrow$ $0-0=0, 1-1=0, 2-2=0$
• 对角线2：(0,1), (1,2), (2,3) $\rightarrow$ $0-1=-1, 1-2=-1, 2-3=-1$
• 对角线3：(1,0), (2,1) $\rightarrow$ $1-0=1, 2-1=1$

结论 1： 凡是属于同一条“左上到右下”对角线的元素，其下标之差 $i - j$ 是一个常数。

第二步：设计“提取-排序-回填”流程

由于 $i-j$ 的范围是 $[-(n-1), m-1]$，我们可以利用这个特征来处理。

1. 提取：遍历一遍矩阵，把相同 $i-j$ 值的元素塞进同一个“桶”（可以用 vector 数组或 map）。
2. 排序：对每个“桶”里的数据进行升序排序。
3. 回填：再次遍历矩阵，根据当前的 $i-j$ 从对应的“桶”里依次取回最小的元素。

第三步：复杂度分析与优化建议

• 时间复杂度：
  • 遍历矩阵：$O(M \times N)$。
  • 排序：矩阵总共有 $M \times N$ 个元素。假设对角线平均长度为 $L$，则排序复杂度约为 $O(M \times N \log L)$。在此题范围内，$L \le \min(M, N)$，效率极高。
• 空间复杂度思考：
  • 我们需要额外的空间存储对角线元素，空间复杂度为 $O(M \times N)$。
  • 优化建议：在 NOI 竞赛中，如果内存极其紧张，可以考虑每次只处理一条对角线，处理完即释放，但这通常不是此类问题的瓶颈。

四、 NOI 风格 C++14 伪代码提示

// 引入必要的库 (iostream, vector, algorithm)
使用命名空间 标准库;

常量整型 最大值 = 205; // 考虑到 i-j 可能为负，需要加偏移量
向量<整型> 桶[最大值];

函数 解决() {
    读取 m, n;
    整型 矩阵[105][105];
    
    // 第一步：读取并提取
    对于 i 从 0 到 m-1:
        对于 j 从 0 到 n-1:
            读取 矩阵[i][j];
            // 使用偏移量 100 保证下标非负
            将 矩阵[i][j] 放入 桶[i - j + 100];

    // 第二步：对每个非空的桶进行排序
    // 提示：你可以遍历桶数组，如果 桶[k] 不为空，则执行 排序(桶[k].开始, 桶[k].结束);
    // 为了方便回填，排序后可以使用反转或者维护一个指针/计数器。

    // 第三步：按顺序回填
    // 再次遍历 (i, j)，根据 i-j+100 找到对应的桶，
    // 取出该桶中当前最小的元素（取完后记得移除或移动指针）。

    // 第四步：输出矩阵
}

五、 总结：读题关键词与题型识别

当你遇到矩阵题目时，如果看到以下关键词，通常可以联想到下标变换：

1. “对角线” (Diagonal)：
   • 左上到右下：$i - j$ 为定值。
   • 左下到右上：$i + j$ 为定值。
2. “升序/降序” (Sort)：暗示需要提取数据进行排序再重新填充。
3. “相邻元素”：暗示可能涉及方向数组（dx, dy）的搜索。

教练点评：这道题的核心在于数学抽象能力。能够从看似杂乱的坐标中发现 $i-j$ 的不变性，就把一个二维空间排序问题转化为了数个一维容器处理问题。这正是算法竞赛中“化繁为简”的精髓。加油！