Longest Increasing Path in a Matrix
Ricevi matrix, una griglia di numeri interi con m righe e n colonne, sotto forma di elenco di righe. Un percorso procede in alto, in basso, a sinistra o a destra (senza diagonali e senza oltrepassare i bordi) e ogni passo deve arrivare a un valore strettamente maggiore. Restituisci il numero di celle del percorso più lungo di questo tipo. Una singola cella costituisce un percorso di 1 cella.
Funzione
- matrixinteger-2d-array
- la griglia di valori, come elenco di righe di uguale lunghezza
- Restituisceinteger
- il numero di celle nel percorso strettamente crescente più lungo
Vincoli
1 ≤ m, n ≤ 100, dovem = matrix.lengthen = matrix[i].length- Ogni riga ha la stessa lunghezza
n. 0 ≤ matrix[i][j] ≤ 231-1
Esempi
- Input
- matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
- Output
- 7
- Spiegazione
- Il percorso 3, 4, 5, 6, 7, 8, 9 scende lungo la colonna di destra, prosegue lungo la riga in basso e risale la colonna centrale fino al 9: 7 celle. Partendo dal valore più piccolo, 1, i percorsi migliori hanno 5 celle.
- Input
- matrix = [[2, 2, 2], [2, 5, 2]]
- Output
- 2
- Spiegazione
- I valori uguali non sono un passo in avanti, quindi nessun percorso passa lungo i 2. Il percorso migliore è un passo da uno dei tre 2 attorno al 5 fino al 5: 2 celle.
- Input
- matrix = [[4, 4], [4, 4], [4, 4]]
- Output
- 1
- Spiegazione
- Ogni valore è 4, quindi non è consentito alcun passo da nessuna parte. Ogni cella da sola è un percorso di 1 cella, e 1 è la risposta.
Per approfondire
Puoi anche restituire le celle di uno dei percorsi più lunghi, insieme alla sua lunghezza?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Un percorso può mai tornare su una cella che ha già visitato? Osserva come cambiano i valori lungo il percorso.
I valori aumentano soltanto, quindi un percorso non ripete mai una cella e il percorso più lungo che parte da una cella non dipende da come ci sei arrivato. È pari a 1 più il percorso più lungo a partire dal migliore dei suoi vicini più grandi.
Calcola quel numero una sola volta per cella e memorizzalo. Puoi riempirlo con una ricerca in profondità sui vicini più grandi, guidata da uno stack creato da te, oppure sbucciare la griglia partendo dalle sue vette, uno strato alla volta, e contare gli strati.
Soluzione
Disegna una freccia da ogni cella a ciascuna cella vicina con valore maggiore. I valori aumentano lungo ogni freccia, quindi nessuna catena di frecce può formare un ciclo: la griglia è un grafo diretto aciclico e la risposta è il suo cammino più lungo. In assenza di cicli, il cammino più lungo da una cella dipende solo da quella cella, quindi lo calcoli una volta per cella: O(m × n).
Segui ogni percorso crescente
Corretto, ma non termina sui test più grandi
Intuizione
Inizia una passeggiata da ogni cella e segui ogni ramo formato da vicini più grandi finché non ce ne sono più; la passeggiata più lunga è la risposta. I valori aumentano a ogni passo, quindi una passeggiata non torna mai a una cella e non serve un insieme di celle visitate.
La passeggiata da una cella viene ripetuta ogni volta che un'altra passeggiata vi passa. In una griglia di 100 × 100 in cui ogni valore è la somma della sua riga e della sua colonna, ogni passo a destra o verso il basso sale, e più di 10^58 passeggiate partono dall'angolo in alto a sinistra.
Algoritmo
- Per ogni cella, inserisci (quella cella, 1) in uno stack.
- Estrai una voce (cella, lunghezza) e aggiorna la risposta con la lunghezza.
- Inserisci (vicino, lunghezza + 1) per ogni vicino all'interno della griglia con un valore strettamente maggiore.
- Ripeti finché lo stack non è vuoto, poi passa alla cella iniziale successiva.
- Restituisci la lunghezza massima trovata.
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 answerRicerca in profondità con memoizzazione usando il tuo stack
Intuizione
Sia best[cell] il numero di celle nel percorso crescente più lungo che inizia lì: 1 + max(best[nb]) tra i vicini più grandi nb, oppure 1 se non ce ne sono. Memorizzarlo è sicuro perché le celle che precedono cell in un percorso sono tutte più piccole e non vengono mai dopo di essa. Nel primo esempio, 9 ottiene 1, 8 ottiene 2, 7 ottiene 3, 6 e 2 ottengono 4, 5 e 1 ottengono 5, 4 ottiene 6 e 3 ottiene 7.
Un percorso può attraversare tutte e 10.000 le celle, troppo per la ricorsione, quindi usa uno stack personale. La cella in cima prova la direzione successiva e aggiunge una vicina più grande non ancora completata. Una volta provate tutte e quattro le direzioni, rimuovila dallo stack e imposta il suo best. Non serve alcun contrassegno «in corso»: ogni cella nello stack è più grande di quella sottostante.
Algoritmo
- Imposta
besta 0 (non è ancora noto) e un contatore delle direzioni a 0 per ogni cella. - Per ogni cella con
bestpari a 0, inseriscila in una pila. - Nella cella in cima, incrementa il suo contatore e inserisci il vicino corrispondente se si trova nella griglia, è più grande e non è terminato.
- Dopo quattro direzioni, rimuovi la cella dalla pila e imposta
besta 1 più il valorebestpiù grande tra i suoi vicini più grandi, oppure a 1. - Restituisci il valore
bestpiù grande.
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 answerRimuovi la griglia dalle sue cime
Intuizione
Costruisci la stessa tabella partendo dai valori più alti, come nell'ordinamento topologico di Kahn. Un picco, una cella senza vicini più grandi, avvia un percorso di 1 cella: livello 1. Rimuovi tutti i picchi; le celle che hanno perso il loro ultimo vicino più grande formano il livello successivo. Ripeti finché la griglia non è vuota. Una cella viene rimossa un turno dopo il suo ultimo vicino più grande, quindi il suo livello è uguale al suo best, e il numero di livelli è la risposta. Nel primo esempio i livelli sono 9; 8; 7; 2 e 6; 1 e 5; 4; 3.
Conta per ogni cella quanti vicini più grandi restano. Rimuovere una cella diminuisce il conteggio di ogni vicino strettamente più piccolo, e un conteggio pari a 0 la inserisce nel livello successivo. Ogni cella viene rimossa una volta: O(m × n), senza stack.
Algoritmo
- Per ogni cella, conta i vicini con un valore maggiore.
- Metti nel livello corrente ogni cella il cui conteggio è 0.
- Finché il livello non è vuoto, incrementa di 1 il conteggio dei livelli. Per ogni cella al suo interno, diminuisci il conteggio di ogni vicino strettamente più piccolo e metti nel livello successivo ogni vicino il cui conteggio raggiunge 0.
- Imposta il livello successivo come livello corrente e ripeti.
- Restituisci il conteggio dei livelli.
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
Trappole e casi limite
- Confrontare con
>=invece che con>. Con due 4 adiacenti, una ricerca esaustiva va avanti e indietro all'infinito, mentre una ricerca con memoizzazione legge una lunghezza ancora in fase di calcolo. - Usare la ricorsione in Python. I valori che si snodano in una griglia di 100 × 100 formano un percorso di 10.000 celle, dieci volte il limite predefinito di 1.000 chiamate.
- Saltare le celle già completate come farebbe una visita flood fill. La lunghezza memorizzata è esattamente ciò di cui ha bisogno la cella corrente.
- Partire solo dal valore più piccolo. Nel primo esempio, l'1 dà 5 celle, ma la risposta, 7, parte dal 3.
- Iniziare le lunghezze da 0. Una griglia con valori tutti uguali ha risposta 1.
Domande frequenti3
Qual è la complessità temporale del problema del percorso crescente più lungo in una matrice?
Tempo e spazio O(m × n), con ricerca in profondità con memoizzazione o con eliminazione progressiva: ogni cella viene completata una volta e controlla i suoi 4 vicini. Provare ogni percorso da ogni cella richiede un tempo esponenziale.
Il Longest Increasing Path in a Matrix è un problema di programmazione dinamica o di grafi?
Entrambi. È il percorso più lungo in un grafo aciclico diretto, ovvero programmazione dinamica su un ordinamento topologico. Ordinare le celle dal valore più grande al più piccolo dà un altro ordinamento valido, al costo di O(m × n × log(m × n)) per l'ordinamento.
In cosa differisce dalla sottosequenza crescente più lunga?
Una sottosequenza può saltare degli elementi, ma ne mantiene l’ordine; qui un percorso deve spostarsi in una cella adiacente, in una qualsiasi delle quattro direzioni. In entrambi i casi, una catena strettamente crescente non può mai ripiegare su sé stessa.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def longestIncreasingPath(matrix):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Output atteso
7