Задача: 1329. Sort the Matrix Diagonally
Сложность: medium

Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].

Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.

Пример:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

👨‍💻 Алгоритм:

1⃣Сохраните размеры матрицы m и n. Создайте хеш-карту из минимальных куч для хранения элементов диагоналей.

2⃣Вставьте значения в хеш-карту, используя разность между индексами строки и столбца как ключ, чтобы собирать элементы на одной и той же диагонали.

3⃣Извлеките значения из хеш-карты и обновите матрицу, заполняя ее отсортированными значениями диагоналей. Верните отсортированную матрицу.

😎 Решение:

class Solution {
    function diagonalSort($mat) {
        $m = count($mat);
        $n = count($mat[0]);
        $diagonals = [];

        for ($row = 0; $row < $m; $row++) {
            for ($col = 0; $col < $n; $col++) {
                $key = $row - $col;
                if (!isset($diagonals[$key])) {
                    $diagonals[$key] = [];
                }
                $diagonals[$key][] = $mat[$row][$col];
            }
        }

        foreach ($diagonals as &$diagonal) {
            sort($diagonal);
        }

        for ($row = 0; $row < $m; $row++) {
            for ($col = 0; $col < $n; $col++) {
                $key = $row - $col;
                $mat[$row][$col] = array_shift($diagonals[$key]);
            }
        }

        return $mat;
    }
}

Ставь 👍 и забирай 📚 Базу знаний