LeetCode 每日一题 ---- 【1329.将矩阵按对角线排序】

1329.将矩阵按对角线排序

方法：模拟

按每个对角线遍历，将得到的值放入数组中，然后对数组排序，再将数组中的元素再放回去就可以了。

需要注意的一个点是：
i - j + m，可以唯一的确定一条对角线，这样处理起来会方便很多

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        List<List<Integer>> list = new ArrayList<>(m + n);
        for (int i = 0; i < m + n; i ++ ) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j < m; j ++ ) {
                list.get(i - j + m).add(mat[i][j]);
            }
        }
        for (List<Integer> d : list) {
            Collections.sort(d, Collections.reverseOrder());
        }
        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j < m; j ++ ) {
                mat[i][j] = list.get(i - j + m).removeLast();
            }
        }
        return mat;
    }
}
/*
i - j + m 唯一的确定了矩阵的对角线（i - j）， + m 实际上是为了防止边界的溢出
00 01 02 03
10 11 12 13
20 21 22 23
*/

时间复杂度：
O( nmlog(min(n,m)) )
n，m 是矩阵的长和宽，矩阵对角线的最大长度是 min(n, m)

空间复杂度：
O(nm)