1329. Sort the Matrix Diagonally

heap O((m+n)max(m, n)log(max(m, n))) time O(mn) space
从右上到左下r - c的差递增，从左上往右下扫描，根据差值存入对应的heap，再扫描一遍取出来即可

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        unordered_map<int, priority_queue<int, vector<int>, greater<>>> hm;
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                hm[r - c].push(mat[r][c]);
            }
        }
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                mat[r][c] = hm[r - c].top();
                hm[r - c].pop();
            }
        }
        return mat;
    }
};

O((m+n)max(m, n)log(max(m, n))) time O(max(m, n)) space
这个方法节省空间，但算边界比较麻烦，外层循环根据r - c的差值递增，内层循环根据r递增，d = r - c，因为0 <= c = r - d <= n - 1所以d <= r <= n - 1 + d并且0 <= r <= m - 1，所以max(d, 0) <= r <= min(m - 1, n - 1 + d)

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        for (int d = 1 - n; d <= m - 1; ++d) {
            vector<int> v;
            for (int r = max(d, 0); r <= min(m - 1, n - 1 + d); ++r) {
                v.push_back(mat[r][r - d]);
            }
            sort(begin(v), end(v), greater());
            for (int r = max(d, 0); r <= min(m - 1, n - 1 + d); ++r) {
                mat[r][r - d] = v.back();
                v.pop_back();
            }
        }
        return mat;
    }
};