Longest Increasing Path in a Matrix
Otrzymujesz matrix, siatkę liczb całkowitych z m wierszami i n kolumnami, w postaci listy wierszy. Ścieżka prowadzi w górę, w dół, w lewo lub w prawo (bez ruchów po przekątnej i bez zawijania na krawędziach), a każdy krok musi prowadzić do ściśle większej wartości. Zwróć liczbę komórek na najdłuższej takiej ścieżce. Pojedyncza komórka to ścieżka o długości 1 komórki.
Funkcja
- matrixinteger-2d-array
- siatka wartości w postaci listy wierszy o tej samej długości
- Zwracainteger
- liczba komórek na najdłuższej ściśle rosnącej ścieżce
Ograniczenia
1 ≤ m, n ≤ 100, gdziem = matrix.lengthin = matrix[i].length- Każdy wiersz ma tę samą długość
n. 0 ≤ matrix[i][j] ≤ 231-1
Przykłady
- Wejście
- matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
- Wyjście
- 7
- Wyjaśnienie
- Ścieżka 3, 4, 5, 6, 7, 8, 9 biegnie w dół prawej kolumny, wzdłuż dolnego wiersza i w górę środkowej kolumny do 9: 7 komórek. Od najmniejszej wartości, 1, najlepsze ścieżki mają 5 komórek.
- Wejście
- matrix = [[2, 2, 2], [2, 5, 2]]
- Wyjście
- 2
- Wyjaśnienie
- Równe wartości nie oznaczają kroku w górę, więc żadna ścieżka nie biegnie po polach z 2. Najlepiej wykonać krok z jednego z trzech pól z 2 wokół 5 na pole z 5: 2 pola.
- Wejście
- matrix = [[4, 4], [4, 4], [4, 4]]
- Wyjście
- 1
- Wyjaśnienie
- Każda wartość wynosi 4, więc nigdzie nie można wykonać żadnego kroku. Każda komórka z osobna stanowi ścieżkę o długości 1 komórki, a odpowiedzią jest 1.
Pytanie dodatkowe
Czy możesz również zwrócić komórki jednej z najdłuższych ścieżek wraz z jej długością?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Czy ścieżka może wrócić do komórki, którą już odwiedziła? Obserwuj, jak po drodze zmieniają się wartości.
Wartości tylko rosną, więc ścieżka nigdy nie przechodzi ponownie przez to samo pole, a najdłuższa ścieżka rozpoczynająca się w danym polu nie zależy od tego, jak do niego dotarłeś. Jej długość to 1 plus długość najdłuższej ścieżki od najlepszego z jego większych sąsiadów.
Oblicz tę liczbę raz dla każdej komórki i zapisz ją. Możesz wypełnić ją, wykonując przeszukiwanie w głąb po większych sąsiadach, sterowane własnym stosem, albo obierać siatkę warstwa po warstwie, zaczynając od jej szczytów, i liczyć warstwy.
Rozwiązanie
Narysuj strzałkę z każdej komórki do każdego większego sąsiada. Wartości rosną wzdłuż każdej strzałki, więc żaden łańcuch strzałek nie może tworzyć pętli: siatka jest skierowanym grafem acyklicznym, a odpowiedzią jest jego najdłuższa ścieżka. Bez cykli najdłuższa ścieżka z komórki zależy tylko od tej komórki, więc obliczasz ją raz dla każdej komórki: O(m × n).
Podążaj każdą rosnącą ścieżką
Poprawne, ale nie kończy się na największych testach
Intuicja
Rozpocznij wędrówkę w każdej komórce i podążaj każdą gałęzią prowadzącą do większego sąsiada, aż żadna nie pozostanie; najdłuższa wędrówka jest odpowiedzią. Wartości rosną na każdym kroku, więc wędrówka nigdy nie wraca do komórki i nie wymaga zbioru odwiedzonych komórek.
Wędrówka z komórki jest powtarzana za każdym razem, gdy przechodzi przez nią inna wędrówka. Na siatce 100 × 100, gdzie każda wartość jest sumą numeru wiersza i kolumny, każdy krok w prawo lub w dół prowadzi do większej wartości, a z lewego górnego rogu wychodzi więcej niż 10^58 wędrówek.
Algorytm
- Dla każdej komórki umieść na stosie parę (komórka, 1).
- Zdejmij wpis (komórka, długość) ze stosu i zaktualizuj odpowiedź, używając długości.
- Umieść na stosie parę (sąsiad, długość + 1) dla każdego sąsiada znajdującego się w siatce i mającego ściśle większą wartość.
- Powtarzaj, aż stos będzie pusty, a następnie przejdź do następnej komórki startowej.
- Zwróć największą napotkaną długość.
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 answerZapamiętywane przeszukiwanie w głąb z własnym stosem
Intuicja
Niech best[cell] oznacza liczbę komórek na najdłuższej ścieżce rosnącej, która zaczyna się w tej komórce: 1 + max(best[nb]) wśród większych sąsiadów nb albo 1, jeśli ich nie ma. Bezpiecznie jest ją zapisać, ponieważ komórki poprzedzające cell na ścieżce są mniejsze i nigdy nie występują po niej. W pierwszym przykładzie 9 otrzymuje 1, 8 otrzymuje 2, 7 otrzymuje 3, 6 i 2 otrzymują 4, 5 i 1 otrzymują 5, 4 otrzymuje 6, a 3 otrzymuje 7.
Ścieżka może przechodzić przez wszystkie 10 000 komórek, co oznacza zbyt dużą głębokość dla rekurencji, więc użyj własnego stosu. Komórka na szczycie stosu sprawdza kolejny kierunek i dodaje na stos większego sąsiada, który nie został jeszcze ukończony. Gdy zostaną sprawdzone wszystkie cztery kierunki, zdejmij ją ze stosu i ustaw jej best. Nie jest potrzebne oznaczenie „w trakcie”: każda komórka na stosie jest większa od komórki poniżej niej.
Algorytm
- Ustaw
bestna 0 (jeszcze nieznane), a licznik kierunków na 0 dla każdej komórki. - Umieść na stosie każdą komórkę, dla której
bestwynosi 0. - W komórce na szczycie stosu zwiększ jej licznik i umieść na stosie tego sąsiada, jeśli znajduje się w siatce, ma większą wartość i nie został jeszcze przetworzony.
- Po sprawdzeniu czterech kierunków zdejmij komórkę ze stosu i ustaw
bestna 1 plus największa wartośćbestwśród jej sąsiadów o większych wartościach albo na 1. - Zwróć największą wartość
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 answerObierz siatkę od jej wierzchołków
Intuicja
Zbuduj tę samą tabelę, zaczynając od największych wartości i schodząc w dół, podobnie jak w sortowaniu topologicznym Kahna. Szczyt, czyli komórka bez większego sąsiada, rozpoczyna ścieżkę o długości 1 komórki: warstwę 1. Usuń wszystkie szczyty; komórki, które straciły ostatniego większego sąsiada, tworzą następną warstwę. Powtarzaj, aż siatka będzie pusta. Komórka trafia do warstwy o jeden poziom niższej niż jej ostatni większy sąsiad, więc jej warstwa jest równa jej best, a liczba warstw to odpowiedź. W pierwszym przykładzie warstwy to: 9; 8; 7; 2 i 6; 1 i 5; 4; 3.
Dla każdej komórki policz, ilu większych sąsiadów jeszcze pozostało. Usunięcie komórki zmniejsza licznik każdego ściśle mniejszego sąsiada, a licznik równy 0 umieszcza komórkę w następnej warstwie. Każda komórka jest usuwana raz: O(m × n), bez stosu.
Algorytm
- Dla każdej komórki policz sąsiadów o większej wartości.
- Umieść każdą komórkę, której licznik wynosi 0, w bieżącej warstwie.
- Dopóki warstwa nie jest pusta, zwiększ licznik warstw o 1. Dla każdej komórki w tej warstwie zmniejsz licznik każdego ściśle mniejszego sąsiada i umieść sąsiada, którego licznik osiągnie 0, w następnej warstwie.
- Ustaw następną warstwę jako bieżącą i powtórz.
- Zwróć licznik warstw.
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
Pułapki i przypadki brzegowe
- Porównywanie za pomocą
>=zamiast>. Przy dwóch sąsiadujących ze sobą czwórkach algorytm brute force porusza się tam i z powrotem w nieskończoność, a wyszukiwanie z memoizacją odczytuje długość, która jest wciąż obliczana. - Rekurencja w Pythonie. Wartości układające się w wężyk na siatce 100 × 100 tworzą ścieżkę o długości 10 000 komórek, co dziesięciokrotnie przekracza domyślny limit 1 000 wywołań.
- Pomijanie przetworzonych komórek, jak zrobiłoby to wypełnianie obszaru. Zapisana dla nich długość jest dokładnie tym, czego potrzebuje bieżąca komórka.
- Rozpoczynanie tylko od najmniejszej wartości. W pierwszym przykładzie 1 daje 5 komórek, ale odpowiedź, 7, zaczyna się od 3.
- Rozpoczynanie długości od 0. Siatka z jednakowymi wartościami ma odpowiedź równą 1.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu najdłuższej rosnącej ścieżki w macierzy?
Czas i pamięć O(m × n), przy użyciu zapamiętującego wyniki przeszukiwania w głąb lub przez obieranie: każda komórka jest przetwarzana raz i sprawdza swoich 4 sąsiadów. Sprawdzanie każdej ścieżki z każdej komórki ma złożoność wykładniczą.
Czy problem najdłuższej rosnącej ścieżki w macierzy jest problemem programowania dynamicznego czy problemem grafowym?
Oba. Jest to najdłuższa ścieżka w skierowanym grafie acyklicznym, czyli programowanie dynamiczne w porządku topologicznym. Posortowanie komórek od największej do najmniejszej wartości daje inny poprawny porządek, kosztem O(m × n × log(m × n)) za sortowanie.
Czym to się różni od najdłuższego rosnącego podciągu?
Podciąg może pomijać elementy, ale zachowuje ich kolejność; tutaj ścieżka musi prowadzić do sąsiedniej komórki, w jednym z czterech kierunków. W obu przypadkach ściśle rosnący łańcuch nie może zapętlić się.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def longestIncreasingPath(matrix):
# Wpisz kod tutajTest #1
Test #2
Test #3
Argument
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Oczekiwany wynik
7