329. Longest Increasing Path in a Matrix
leetcode hard
#array#csharp#graph#hard#leetcode#matrix#search#sort
Task
Дана матрица целых чисел размером 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].
C# solution
matched/originalpublic class Solution {
private static readonly int[][] dir = new int[][] {
new int[] {0, 1}, new int[] {1, 0},
new int[] {0, -1}, new int[] {-1, 0}
};
public int LongestIncreasingPath(int[][] matrix) {
int m = matrix.Length;
if (m == 0) return 0;
int n = matrix[0].Length;
int[][] outdegree = new int[m + 2][];
for (int i = 0; i < outdegree.Length; i++)
outdegree[i] = new int[n + 2];
int[][] newMatrix = new int[m + 2][];
for (int i = 0; i < newMatrix.Length; i++)
newMatrix[i] = new int[n + 2];
for (int i = 0; i < m; ++i) {
Array.Copy(matrix[i], 0, newMatrix[i + 1], 1, n);
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
foreach (var d in dir) {
if (newMatrix[i][j] < newMatrix[i + d[0]][j + d[1]]) {
outdegree[i][j]++;
}
}
}
}
List<int[]> leaves = new List<int[]>();
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (outdegree[i][j] == 0) leaves.Add(new int[] { i, j });
}
}
int height = 0;
while (leaves.Count > 0) {
height++;
List<int[]> newLeaves = new List<int[]>();
foreach (var node in leaves) {
foreach (var d in dir) {
int x = node[0] + d[0], y = node[1] + d[1];
if (newMatrix[node[0]][node[1]] > newMatrix[x][y]) {
outdegree[x][y]--;
if (outdegree[x][y] == 0) newLeaves.Add(new int[] { x, y });
}
}
}
leaves = newLeaves;
}
return height;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private static readonly int[][] dir = new int[][] {
new int[] {0, 1}, new int[] {1, 0},
new int[] {0, -1}, new int[] {-1, 0}
};
public int LongestIncreasingPath(int[][] matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
int[][] outdegree = new int[m + 2][];
for (int i = 0; i < outdegree.size(); i++)
outdegree[i] = new int[n + 2];
int[][] newMatrix = new int[m + 2][];
for (int i = 0; i < newMatrix.size(); i++)
newMatrix[i] = new int[n + 2];
for (int i = 0; i < m; ++i) {
Array.Copy(matrix[i], 0, newMatrix[i + 1], 1, n);
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
foreach (var d in dir) {
if (newMatrix[i][j] < newMatrix[i + d[0]][j + d[1]]) {
outdegree[i][j]++;
}
}
}
}
List<int[]> leaves = new List<int[]>();
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (outdegree[i][j] == 0) leaves.push_back(new int[] { i, j });
}
}
int height = 0;
while (leaves.size() > 0) {
height++;
List<int[]> newLeaves = new List<int[]>();
foreach (var node in leaves) {
foreach (var d in dir) {
int x = node[0] + d[0], y = node[1] + d[1];
if (newMatrix[node[0]][node[1]] > newMatrix[x][y]) {
outdegree[x][y]--;
if (outdegree[x][y] == 0) newLeaves.push_back(new int[] { x, y });
}
}
}
leaves = newLeaves;
}
return height;
}
}Java solution
matched/originalpublic class Solution {
private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int m, n;
public int longestIncreasingPath(int[][] grid) {
int m = grid.length;
if (m == 0) return 0;
int n = grid[0].length;
int[][] matrix = new int[m + 2][n + 2];
for (int i = 0; i < m; ++i)
System.arraycopy(grid[i], 0, matrix[i + 1], 1, n);
int[][] outdegree = new int[m + 2][n + 2];
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
for (int[] d: dir)
if (matrix[i][j] < matrix[i + d[0]][j + d[1]])
outdegree[i][j]++;
n += 2;
m += 2;
List<int[]> leaves = new ArrayList<>();
for (int i = 1; i < m - 1; ++i)
for (int j = 1; j < n - 1; ++j)
if (outdegree[i][j] == 0) leaves.add(new int[]{i, j});
int height = 0;
while (!leaves.isEmpty()) {
height++;
List<int[]> newLeaves = new ArrayList<>();
for (int[] node : leaves) {
for (int[] d:dir) {
int x = node[0] + d[0], y = node[1] + d[1];
if (matrix[node[0]][node[1]] > matrix[x][y])
if (--outdegree[x][y] == 0)
newLeaves.add(new int[]{x, y});
}
}
leaves = newLeaves;
}
return height;
}
}JavaScript solution
matched/originalvar 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;
};Go solution
matched/originalvar dir = [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
func longestIncreasingPath(matrix [][]int) int {
m := len(matrix)
if m == 0 {
return 0
}
n := len(matrix[0])
outdegree := make([][]int, m+2)
newMatrix := make([][]int, m+2)
for i := range outdegree {
outdegree[i] = make([]int, n+2)
newMatrix[i] = make([]int, n+2)
}
for i := 0; i < m; i++ {
copy(newMatrix[i+1][1:], matrix[i])
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
for _, d := range dir {
if newMatrix[i][j] < newMatrix[i+d[0]][j+d[1]] {
outdegree[i][j]++
}
}
}
}
var leaves [][]int
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if outdegree[i][j] == 0 {
leaves = append(leaves, []int{i, j})
}
}
}
height := 0
for len(leaves) > 0 {
height++
var newLeaves [][]int
for _, node := range leaves {
for _, d := range dir {
x, y := node[0]+d[0], node[1]+d[1]
if newMatrix[node[0]][node[1]] > newMatrix[x][y] {
outdegree[x][y]--
if outdegree[x][y] == 0 {
newLeaves = append(newLeaves, []int{x, y})
}
}
}
}
leaves = newLeaves
}
return height
}Explanation
Algorithm
Инициализация и создание матрицы:
Инициализируйте размеры матрицы m и n. Создайте матрицу matrix с добавленными границами (нулевыми значениями) вокруг исходной матрицы, чтобы избежать выхода за пределы при обработке.
Рассчитайте количество исходящих связей (outdegrees) для каждой клетки и сохраните их в outdegree.
Поиск начальных листьев:
Найдите все клетки с нулевыми исходящими связями и добавьте их в список leaves. Эти клетки будут начальной точкой для "слоевого удаления".
Удаление слоев:
Повторяйте процесс удаления клеток уровня за уровнем в порядке топологической сортировки, пока не останется листьев. Обновляйте количество исходящих связей и добавляйте новые листья на следующем уровне. Подсчитывайте количество уровней, что в итоге даст длину самого длинного возрастающего пути.
😎