Задача: 498. Diagonal Traverse
Сложность: medium

Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке.

Пример:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

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

1⃣Инициализация и подготовка
Проверьте, пуста ли матрица. Инициализируйте переменные для хранения размеров матрицы. Создайте массив result для хранения окончательных результатов и временный список intermediate для промежуточных значений диагоналей.

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

3⃣Обработка диагоналей
Для каждой диагонали сохраните её элементы в списке intermediate. Переверните элементы диагонали, если её номер чётный. Добавьте элементы диагонали в массив result.

😎 Решение:

class Solution {
    function findDiagonalOrder($mat) {
        if (empty($mat) || empty($mat[0])) return [];
        $N = count($mat);
        $M = count($mat[0]);
        $result = [];
        
        for ($d = 0; $d < $N + $M - 1; $d++) {
            $intermediate = [];
            $r = $d < $M ? 0 : $d - $M + 1;
            $c = $d < $M ? $d : $M - 1;
            
            while ($r < $N && $c >= 0) {
                $intermediate[] = $mat[$r][$c];
                $r++;
                $c--;
            }
            
            if ($d % 2 == 0) {
                $intermediate = array_reverse($intermediate);
            }
            $result = array_merge($result, $intermediate);
        }
        
        return $result;
    }
}

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