Задача: 329. Longest Increasing Path in a Matrix
Сложность: hard

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

Пример:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

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

1⃣Инициализация и создание матрицы:
Инициализируйте размеры матрицы m и n. Создайте матрицу matrix с добавленными границами (нулевыми значениями) вокруг исходной матрицы, чтобы избежать выхода за пределы при обработке.
Рассчитайте количество исходящих связей (outdegrees) для каждой клетки и сохраните их в outdegree.

2⃣Поиск начальных листьев:
Найдите все клетки с нулевыми исходящими связями и добавьте их в список leaves. Эти клетки будут начальной точкой для "слоевого удаления".

3⃣Удаление слоев:
Повторяйте процесс удаления клеток уровня за уровнем в порядке топологической сортировки, пока не останется листьев. Обновляйте количество исходящих связей и добавляйте новые листья на следующем уровне. Подсчитывайте количество уровней, что в итоге даст длину самого длинного возрастающего пути.

😎 Решение:

var longestIncreasingPath = function(matrix) {
    if (!matrix.length) return 0;
    const m = matrix.length, n = matrix[0].length;
    const outdegree = Array.from({ length: m + 2 }, () => Array(n + 2).fill(0));
    const newMatrix = Array.from({ length: m + 2 }, () => Array(n + 2).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            newMatrix[i + 1][j + 1] = matrix[i][j];
        }
    }

    const dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            for (const [dx, dy] of dir) {
                if (newMatrix[i][j] < newMatrix[i + dx][j + dy]) {
                    outdegree[i][j]++;
                }
            }
        }
    }

    const leaves = [];
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (outdegree[i][j] === 0) leaves.push([i, j]);
        }
    }

    let height = 0;
    while (leaves.length) {
        height++;
        const newLeaves = [];
        for (const [i, j] of leaves) {
            for (const [dx, dy] of dir) {
                const x = i + dx, y = j + dy;
                if (newMatrix[i][j] > newMatrix[x][y]) {
                    outdegree[x][y]--;
                    if (outdegree[x][y] === 0) newLeaves.push([x, y]);
                }
            }
        }
        leaves.length = 0;
        leaves.push(...newLeaves);
    }

    return height;
};

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