Longest Increasing Path in a Matrix
Tu reçois matrix, une grille de nombres entiers comportant m lignes et n colonnes, sous forme de liste de lignes. Un chemin avance vers le haut, le bas, la gauche ou la droite (pas de diagonales ni de passage d’un bord à l’autre), et chaque étape doit aboutir à une valeur strictement supérieure. Renvoie le nombre de cellules du plus long chemin de ce type. Une seule cellule constitue un chemin de 1 cellule.
Fonction
- matrixinteger-2d-array
- la grille de valeurs, sous forme de liste de lignes de même longueur
- Renvoieinteger
- le nombre de cellules du plus long chemin strictement croissant
Contraintes
1 ≤ m, n ≤ 100, oùm = matrix.lengthetn = matrix[i].length- Chaque ligne a la même longueur
n. 0 ≤ matrix[i][j] ≤ 231-1
Exemples
- Entrée
- matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
- Sortie
- 7
- Explication
- Le chemin 3, 4, 5, 6, 7, 8, 9 descend le long de la colonne de droite, suit la rangée du bas et remonte la colonne du milieu jusqu’au 9 : 7 cellules. À partir de la plus petite valeur, 1, les meilleurs chemins comptent 5 cellules.
- Entrée
- matrix = [[2, 2, 2], [2, 5, 2]]
- Sortie
- 2
- Explication
- Les valeurs égales ne constituent pas un pas vers le haut, donc aucun chemin ne passe le long des 2. Le meilleur chemin fait un pas depuis l’un des trois 2 autour du 5 jusqu’au 5 : 2 cases.
- Entrée
- matrix = [[4, 4], [4, 4], [4, 4]]
- Sortie
- 1
- Explication
- Chaque valeur est 4, donc aucune étape n’est autorisée. Chaque cellule seule forme un chemin d’une cellule, et 1 est la réponse.
Pour aller plus loin
Peux-tu également renvoyer les cellules de l’un des plus longs chemins, ainsi que sa longueur ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Un chemin peut-il revenir sur une cellule qu’il a déjà visitée ? Observe l’évolution des valeurs tout au long du parcours.
Les valeurs ne font qu’augmenter, donc un chemin ne repasse jamais par une même cellule, et le plus long chemin qui commence dans une cellule ne dépend pas de la façon dont vous y êtes arrivé. Il est égal à 1 plus le plus long chemin à partir de son meilleur voisin de valeur supérieure.
Calcule ce nombre une seule fois par cellule et stocke-le. Soit tu le remplis à l’aide d’une recherche en profondeur sur les voisins plus grands, pilotée par ta propre pile, soit tu épluches la grille depuis ses sommets, une couche à la fois, et tu comptes les couches.
Solution
Tracez une flèche de chaque cellule vers chacun de ses voisins plus grands. Les valeurs augmentent le long de chaque flèche, donc aucune chaîne de flèches ne peut former une boucle : la grille est un graphe orienté acyclique, et la réponse est son plus long chemin. En l’absence de cycles, le plus long chemin à partir d’une cellule dépend uniquement de cette cellule, donc vous le calculez une seule fois par cellule : O(m × n).
Suivez chaque chemin croissant
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Commence un parcours à chaque cellule et suis chaque branche vers des voisins de valeur supérieure jusqu’à ce qu’il n’y en ait plus ; le parcours le plus long est la réponse. Les valeurs augmentent à chaque étape, donc un parcours ne revient jamais à une cellule et n’a pas besoin d’un ensemble des cellules visitées.
Le parcours à partir d’une cellule est refait chaque fois qu’un autre parcours passe par cette cellule. Sur une grille de 100 × 100 où chaque valeur est la somme de sa ligne et de sa colonne, chaque pas vers la droite ou vers le bas fait monter, et plus de 10^58 parcours partent du coin supérieur gauche.
Algorithme
- Pour chaque cellule, empilez (cette cellule, 1).
- Dépilez une entrée (cellule, longueur) et mettez à jour la réponse avec la longueur.
- Empilez (voisin, longueur + 1) pour chaque voisin dans la grille ayant une valeur strictement supérieure.
- Répétez jusqu’à ce que la pile soit vide, puis passez à la cellule de départ suivante.
- Retournez la plus grande longueur observée.
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
answer = 0
for sr in range(rows):
for sc in range(cols):
# Each entry is one path in progress: the cell it ends on and
# how many cells it has.
stack = [(sr, sc, 1)]
while stack:
r, c, length = stack.pop()
answer = max(answer, length)
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
stack.append((nr, nc, length + 1))
return answerRecherche en profondeur avec mémoïsation et votre propre pile
Intuition
Soit best[cell] le nombre de cellules du plus long chemin croissant qui commence à cet endroit : 1 + max(best[nb]) parmi les voisins plus grands nb, ou 1 s’il n’y en a aucun. Il est sûr de stocker cette valeur, car les cellules qui précèdent cell dans un chemin sont toutes plus petites et ne viennent jamais après elle. Dans le premier exemple, 9 obtient 1, 8 obtient 2, 7 obtient 3, 6 et 2 obtiennent 4, 5 et 1 obtiennent 5, 4 obtient 6 et 3 obtient 7.
Un chemin peut aussi traverser les 10 000 cellules, ce qui est trop profond pour la récursion : utilisez donc votre propre pile. La cellule au sommet essaie la direction suivante et empile un voisin plus grand qui n’est pas terminé. Une fois les quatre directions essayées, dépilez-la et définissez son best. Aucun marqueur « en cours » n’est nécessaire : chaque cellule de la pile est plus grande que celle qui se trouve en dessous.
Algorithme
- Initialise
bestà 0 (pas encore connu) et un compteur de directions à 0 pour chaque cellule. - Pour chaque cellule dont
bestvaut 0, empile-la. - Sur la cellule au sommet, avance son compteur et empile ce voisin s’il se trouve dans la grille, est plus grand et n’est pas terminé.
- Après les quatre directions, dépile la cellule et définis
bestà 1 plus le plus grandbestparmi ses voisins plus grands, ou à 1. - Renvoie le plus grand
best.
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
# best[r][c]: cells on the longest increasing path that starts at (r, c).
# 0 means not known yet.
best = [[0] * cols for _ in range(rows)]
# step[r][c]: how many of the 4 directions the search has tried from (r, c).
step = [[0] * cols for _ in range(rows)]
answer = 0
for sr in range(rows):
for sc in range(cols):
if best[sr][sc]:
continue
# Our own stack instead of recursion: a path can be thousands of
# cells long, past Python's limit of 1,000 nested calls.
stack = [(sr, sc)]
while stack:
r, c = stack[-1]
d = step[r][c]
if d < 4:
step[r][c] = d + 1
nr, nc = r + dirs[d][0], c + dirs[d][1]
# The stack only climbs, so a larger neighbour is never on it.
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
stack.append((nr, nc))
continue
# Every larger neighbour is finished: build on the best of them.
stack.pop()
length = 1
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
length = max(length, best[nr][nc] + 1)
best[r][c] = length
answer = max(answer, length)
return answerRetirez la grille à partir de ses sommets
Intuition
Construisez le même tableau en partant des valeurs les plus élevées, comme dans le tri topologique de Kahn. Un sommet, une cellule sans voisin plus grand, commence un chemin d'une cellule : couche 1. Supprimez tous les sommets ; les cellules qui ont perdu leur dernier voisin plus grand forment la couche suivante. Répétez jusqu'à ce que la grille soit vide. Une cellule est supprimée un tour après son dernier voisin plus grand, donc sa couche est égale à son best, et le nombre de couches est la réponse. Dans le premier exemple, les couches sont : 9 ; 8 ; 7 ; 2 et 6 ; 1 et 5 ; 4 ; 3.
Comptez, pour chaque cellule, le nombre de voisins plus grands qui restent. La suppression d'une cellule diminue le compte de chaque voisin strictement plus petit, et un compte de 0 la place dans la couche suivante. Chaque cellule est supprimée une seule fois : O(m × n), sans pile.
Algorithme
- Pour chaque cellule, comptez les voisins dont la valeur est supérieure.
- Placez dans la couche actuelle chaque cellule dont le compte est égal à 0.
- Tant que la couche n’est pas vide, ajoutez 1 au nombre de couches. Pour chaque cellule qu’elle contient, diminuez le compte de chaque voisin strictement plus petit et placez dans la couche suivante tout voisin dont le compte atteint 0.
- Faites de la couche suivante la couche actuelle et recommencez.
- Renvoyez le nombre de couches.
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
# higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
higher = [[0] * cols for _ in range(rows)]
layer = []
for r in range(rows):
for c in range(cols):
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
higher[r][c] += 1
# A peak: no neighbour is larger, so a path from it has one cell.
if higher[r][c] == 0:
layer.append((r, c))
layers = 0
while layer:
layers += 1
next_layer = []
for r, c in layer:
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
higher[nr][nc] -= 1
# Its last larger neighbour is peeled: it is a peak now.
if higher[nr][nc] == 0:
next_layer.append((nr, nc))
layer = next_layer
# Each layer is one step further from a peak; the count is the longest path.
return layers
Pièges et cas limites
- Comparer avec
>=au lieu de>. Avec deux 4 voisins, une recherche par force brute fait des allers-retours à l’infini, et une recherche avec mémoïsation lit une longueur encore en cours de calcul. - Utiliser la récursivité en Python. Des valeurs qui serpentent dans une grille de 100 × 100 forment un chemin de 10 000 cellules, soit dix fois la limite par défaut de 1 000 appels.
- Ignorer les cellules déjà terminées comme le ferait un remplissage par propagation. Leur longueur mémorisée est exactement ce dont la cellule actuelle a besoin.
- Commencer uniquement par la plus petite valeur. Dans le premier exemple, le 1 donne 5 cellules, mais la réponse, 7, commence par le 3.
- Commencer les longueurs à 0. Une grille de valeurs égales a pour réponse 1.
Questions fréquentes3
Quelle est la complexité temporelle du plus long chemin croissant dans une matrice ?
Temps et espace O(m × n), avec une recherche en profondeur mémorisée ou par élagage : chaque cellule est traitée une fois et examine ses 4 voisines. Essayer tous les chemins à partir de chaque cellule entraîne une complexité exponentielle.
Le plus long chemin croissant dans une matrice relève-t-il de la programmation dynamique ou d’un problème de graphe ?
Les deux. C’est le chemin le plus long dans un graphe orienté acyclique, ce qui relève de la programmation dynamique sur un ordre topologique. Trier les cellules par ordre décroissant de valeur donne un autre ordre valide, au prix d’un coût de O(m × n × log(m × n)) pour le tri.
En quoi cela diffère-t-il de la plus longue sous-séquence croissante ?
Une sous-séquence peut omettre des éléments tout en conservant leur ordre ; ici, un chemin doit passer à une cellule adjacente, dans l’une des quatre directions. Dans les deux cas, une chaîne strictement croissante ne peut jamais revenir sur elle-même en boucle.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def longestIncreasingPath(matrix):
# Écrivez le code iciTest #1
Test #2
Test #3
Argument
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Résultat attendu
7