Longest Increasing Path in a Matrix
Du erhältst matrix, ein Raster aus ganzen Zahlen mit m Zeilen und n Spalten, als Liste von Zeilen. Ein Pfad verläuft nach oben, unten, links oder rechts (keine Diagonalen, kein Überschreiten der Ränder), und jeder Schritt muss auf einem strikt größeren Wert landen. Gib die Anzahl der Zellen auf dem längsten solchen Pfad zurück. Eine einzelne Zelle bildet einen Pfad mit 1 Zelle.
Funktion
- matrixinteger-2d-array
- das Raster aus Werten, als Liste gleich langer Zeilen
- Gibt zurückinteger
- die Anzahl der Zellen auf dem längsten streng ansteigenden Pfad
Einschränkungen
1 ≤ m, n ≤ 100, wobeim = matrix.lengthundn = matrix[i].length- Jede Zeile hat dieselbe Länge
n. 0 ≤ matrix[i][j] ≤ 231-1
Beispiele
- Eingabe
- matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
- Ausgabe
- 7
- Erklärung
- Der Pfad 3, 4, 5, 6, 7, 8, 9 verläuft die rechte Spalte hinunter, entlang der untersten Zeile und die mittlere Spalte hinauf bis zur 9: 7 Zellen. Vom kleinsten Wert, 1, aus haben die besten Pfade 5 Zellen.
- Eingabe
- matrix = [[2, 2, 2], [2, 5, 2]]
- Ausgabe
- 2
- Erklärung
- Gleiche Werte bedeuten keinen Schritt nach oben, daher verläuft kein Pfad entlang der 2en. Am besten ist ein Schritt von einer der drei 2en rund um die 5 zur 5: 2 Zellen.
- Eingabe
- matrix = [[4, 4], [4, 4], [4, 4]]
- Ausgabe
- 1
- Erklärung
- Jeder Wert ist 4, daher ist an keiner Stelle ein Schritt erlaubt. Jede Zelle für sich ist ein Pfad aus 1 Zelle, und 1 ist die Antwort.
Weiterführende Frage
Können Sie auch die Zellen eines längsten Pfads zusammen mit seiner Länge zurückgeben?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Kann ein Pfad jemals zu einer Zelle zurückkehren, die er bereits besucht hat? Beobachte, wie sich die Werte auf dem Weg verändern.
Die Werte steigen nur an, daher wiederholt ein Pfad niemals eine Zelle, und der längste Pfad, der an einer Zelle beginnt, hängt nicht davon ab, wie du dorthin gelangt bist. Er ist 1 plus der längste Pfad vom besten seiner größeren Nachbarn.
Berechne diese Zahl einmal pro Zelle und speichere sie. Fülle sie entweder mithilfe einer Tiefensuche über größere Nachbarn, die von deinem eigenen Stack gesteuert wird, oder schäle das Gitter Schicht für Schicht von seinen Spitzen ab und zähle die Schichten.
Lösung
Zeichne von jeder Zelle einen Pfeil zu jedem größeren Nachbarn. Entlang jedes Pfeils steigen die Werte an, daher kann keine Pfeilkette eine Schleife bilden: Das Raster ist ein gerichteter azyklischer Graph, und die Antwort ist sein längster Pfad. Ohne Zyklen hängt der längste Pfad von einer Zelle nur von dieser Zelle ab, daher berechnest du ihn einmal pro Zelle: O(m × n).
Folge jedem aufsteigenden Pfad
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Beginne an jeder Zelle einen Pfad und folge jedem Zweig zu größeren Nachbarn, bis keiner mehr übrig ist; der längste Pfad ist die Antwort. Die Werte steigen bei jedem Schritt, daher kehrt ein Pfad nie zu einer Zelle zurück und benötigt keine Menge bereits besuchter Zellen.
Der Pfad ab einer Zelle wird jedes Mal erneut durchlaufen, wenn ein anderer Pfad durch sie führt. Auf einem Raster mit 100 × 100 Zellen, bei dem jeder Wert die Summe seiner Zeile und Spalte ist, führt jeder Schritt nach rechts oder nach unten aufwärts, und mehr als 10^58 Pfade gehen von der linken oberen Ecke aus.
Algorithmus
- Lege für jede Zelle (diese Zelle, 1) auf einen Stapel.
- Nimm einen Eintrag (Zelle, Länge) vom Stapel und aktualisiere die Antwort mit der Länge.
- Lege für jeden Nachbarn innerhalb des Gitters mit einem strikt größeren Wert (Nachbar, Länge + 1) auf den Stapel.
- Wiederhole dies, bis der Stapel leer ist, und gehe dann zur nächsten Startzelle.
- Gib die größte gefundene Länge zurück.
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 answerMemoisierte Tiefensuche mit einem eigenen Stack
Idee
Sei best[cell] die Anzahl der Zellen auf dem längsten ansteigenden Pfad, der dort beginnt: 1 + max(best[nb]) über die größeren Nachbarn nb, oder 1, wenn es keine gibt. Das Speichern dieses Werts ist sicher, weil die Zellen vor cell auf einem Pfad alle kleiner sind und nie danach kommen. Im ersten Beispiel erhält 9 den Wert 1, 8 den Wert 2, 7 den Wert 3, 6 und 2 den Wert 4, 5 und 1 den Wert 5, 4 den Wert 6 und 3 den Wert 7.
Ein Pfad kann auch durch alle 10.000 Zellen führen – für Rekursion ist das zu tief, also verwende einen eigenen Stack. Die oberste Zelle probiert ihre nächste Richtung aus und legt einen größeren Nachbarn, der noch nicht fertig ist, auf den Stack. Sobald alle vier Richtungen ausprobiert wurden, entfernst du die Zelle vom Stack und setzt ihren Wert für best. Eine Markierung „in Bearbeitung“ ist nicht nötig: Jede Zelle auf dem Stack ist größer als die darunterliegende.
Algorithmus
- Setze
bestauf 0 (noch nicht bekannt) und einen Richtungszähler für jede Zelle auf 0. - Lege jede Zelle mit
best0 auf einen Stapel. - Erhöhe beim obersten Feld den Zähler und lege den Nachbarn auf den Stapel, wenn er sich innerhalb des Gitters befindet, größer und noch nicht fertig ist.
- Nach vier Richtungen nimm die Zelle vom Stapel und setze
bestauf 1 plus den größtenbest-Wert unter ihren größeren Nachbarn oder auf 1. - Gib den größten
best-Wert zurück.
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 answerSchäle das Raster von seinen Spitzen ab
Idee
Baue dieselbe Tabelle von den höchsten Werten abwärts auf, wie bei Kahns topologischer Sortierung. Ein Gipfel, also eine Zelle ohne größeren Nachbarn, beginnt einen Pfad aus 1 Zelle: Schicht 1. Entferne alle Gipfel; Zellen, die ihren letzten größeren Nachbarn verloren haben, bilden die nächste Schicht. Wiederhole dies, bis das Raster leer ist. Eine Zelle wird eine Runde nach ihrem letzten größeren Nachbarn entfernt, daher entspricht ihre Schicht ihrem best-Wert, und die Anzahl der Schichten ist die Antwort. Im ersten Beispiel sind die Schichten 9; 8; 7; 2 und 6; 1 und 5; 4; 3.
Zähle für jede Zelle, wie viele größere Nachbarn noch vorhanden sind. Wenn eine Zelle entfernt wird, verringert sich der Zähler jedes strikt kleineren Nachbarn; bei einem Zählerstand von 0 kommt die Zelle in die nächste Schicht. Jede Zelle wird einmal entfernt: O(m × n), ohne Stack.
Algorithmus
- Zähle für jede Zelle die Nachbarn mit einem größeren Wert.
- Füge jede Zelle, deren Zähler 0 ist, der aktuellen Ebene hinzu.
- Solange die Ebene nicht leer ist, erhöhe den Ebenenzähler um 1. Verringere für jede Zelle darin den Zähler jedes strikt kleineren Nachbarn und füge einen Nachbarn, dessen Zähler 0 erreicht, der nächsten Ebene hinzu.
- Mache die nächste Ebene zur aktuellen Ebene und wiederhole den Vorgang.
- Gib den Ebenenzähler zurück.
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
Stolperfallen und Grenzfälle
- Vergleich mit
>=statt mit>. Bei zwei benachbarten 4ern läuft eine Brute-Force-Suche endlos hin und her, und eine memoisiert suchende Suche liest eine Länge, die noch berechnet wird. - Rekursion in Python. Werte, die sich durch ein 100 × 100-Raster schlängeln, ergeben einen Pfad aus 10.000 Zellen, zehnmal so viele wie das Standardlimit von 1.000 Aufrufen.
- Fertige Zellen überspringen, wie es eine Flutfüllung tun würde. Ihre gespeicherte Länge ist genau das, was die aktuelle Zelle braucht.
- Nur beim kleinsten Wert anfangen. Im ersten Beispiel ergibt die 1 fünf Zellen, aber die Antwort, 7, beginnt bei der 3.
- Längen bei 0 beginnen lassen. Ein Raster mit gleichen Werten hat die Antwort 1.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität des längsten aufsteigenden Pfads in einer Matrix?
O(m × n) Zeit- und Speicherbedarf, mit memoisierter Tiefensuche oder durch schichtweises Entfernen: Jede Zelle wird genau einmal abgearbeitet und betrachtet ihre 4 Nachbarn. Jeden Pfad von jeder Zelle aus auszuprobieren, ist exponentiell.
Ist der längste aufsteigende Pfad in einer Matrix ein Problem der dynamischen Programmierung oder ein Graphproblem?
Beides. Es ist der längste Pfad in einem gerichteten azyklischen Graphen, also dynamische Programmierung über eine topologische Ordnung. Das Sortieren der Zellen nach absteigendem Wert ergibt eine weitere gültige Reihenfolge, allerdings mit einem Aufwand von O(m × n × log(m × n)) für die Sortierung.
Worin unterscheidet sich das von der längsten aufsteigenden Teilsequenz?
Eine Teilsequenz darf Elemente auslassen, behält aber ihre Reihenfolge bei; ein Pfad muss hier zu einer angrenzenden Zelle führen, und zwar in eine von vier Richtungen. In beiden Fällen kann eine streng ansteigende Kette niemals zu sich selbst zurückführen.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def longestIncreasingPath(matrix):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Erwartete Ausgabe
7