Longest Increasing Path in a Matrix

TrudneProgramowanie dynamiczne Grafy Sortowanie topologiczne

+10

Otrzymujesz matrix, siatkę liczb całkowitych z m wierszami i n kolumnami, w postaci listy wierszy. Ścieżka prowadzi z jednej komórki do drugiej, za każdym razem o jeden krok w górę, w dół, w lewo lub w prawo (bez ruchów po przekątnej i bez przechodzenia na przeciwległą krawędź), a każdy krok musi prowadzić do komórki o ściśle większej wartości. Zwróć liczbę komórek na najdłuższej takiej ścieżce. Pojedyncza komórka sama w sobie tworzy ścieżkę o długości 1 komórki.

Funkcja

longestIncreasingPath(matrix: integer-2d-array) → integer

matrixinteger-2d-array: siatka wartości w postaci listy wierszy o jednakowej długości
Zwracainteger: liczba komórek na najdłuższej ściśle rosnącej ścieżce

Ograniczenia

1 ≤ m, n ≤ 100, gdzie m = matrix.length i n = matrix[i].length
Każdy wiersz ma tę samą długość n.
0 ≤ matrix[i][j] ≤ 2³¹-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ół prawą kolumną, w lewo dolnym wierszem, w górę środkową kolumną i w lewo do 9 w rogu: 7 komórek. Najmniejsza wartość wypada gorzej: od 1 najlepsze ścieżki to 1, 2, 7, 8, 9 oraz 1, 6, 7, 8, 9, każda po 5 komórek.

+18 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz również zwrócić komórki jednej z najdłuższych ścieżek, a nie tylko jej długość?

Rozwiązanie

Narysuj strzałkę z każdej komórki do każdego sąsiada, który zawiera większą wartość. Wartości rosną wzdłuż każdej strzałki, więc żaden łańcuch strzałek nie może prowadzić z powrotem do miejsca, w którym się zaczął: siatka jest skierowanym grafem acyklicznym, a zadanie polega na znalezieniu jego najdłuższej ścieżki. W przypadku ogólnego grafu to pytanie jest beznadziejne dla dużych danych wejściowych, ale gdy nie ma 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, a cały problem sprowadza się do O(m × n). Zapamiętujące wyniki przeszukiwanie w głąb oblicza ją od góry do dołu; usuwanie kolejnych komórek z siatki, zaczynając od jej szczytów, czyli algorytm Kahna w odwrotnym kierunku, oblicza ją od dołu do góry.

Podążaj każdą rosnącą ścieżką

Poprawne, ale nie kończy się na największych testach

Intuicja

Rozpocznij spacer w każdej komórce. Z komórki, w której jesteś, spróbuj przejść do każdego z czterech sąsiadów o większej wartości, a następnie idź dalej w ten sam sposób, aż nie zostanie żaden sąsiad o większej wartości. Policz komórki w każdym spacerze i zachowaj największą liczbę.

Spacer nie wymaga zbioru odwiedzonych komórek. Wartości rosną przy każdym kroku, więc spacer nigdy nie może wrócić do komórki: aby ponownie się w niej znaleźć, musiałby wrócić do jej wartości. Przechowuj spacery na stosie wpisów (komórka, długość). Zdjęcie wpisu ze stosu kończy spacer w danej komórce, a dodanie jej sąsiadów o większych wartościach go wydłuża.

Ta metoda jest poprawna i beznadziejnie powolna, ponieważ spacery rozgałęziają się. Na siatce 100 × 100, w której każda wartość jest sumą numeru wiersza i numeru kolumny, każdy krok w prawo lub w dół prowadzi do większej wartości, a liczba spacerów z samego lewego górnego rogu przekracza 10^58. Co gorsza, spacer z dowolnej komórki jest powtarzany za każdym razem, gdy przechodzi przez nią inny spacer, a właśnie to marnotrawstwo eliminuje następne podejście.

Algorytm

Dla każdej komórki umieść (that cell, 1) na stosie.
Zdejmij wpis (cell, length) ze stosu i zaktualizuj odpowiedź, używając length.
Umieść (neighbour, length + 1) dla każdego sąsiada w siatce o ściśle większej wartości.
Powtarzaj, aż stos będzie pusty, a następnie przejdź do następnej komórki początkowej.
Zwróć największą zaobserwowaną wartość length.

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 answer

Memoizowane 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. Ścieżka kończy się w niej albo jej następny krok prowadzi do większego sąsiada, a potem biegnie dalej najdłuższą ścieżką od tego sąsiada. Zatem best[cell] = 1 + max(best[nb]) dla większych sąsiadów nb, a jeśli ich nie ma, wartość wynosi 1. Można bezpiecznie ponownie wykorzystać ten wynik dzięki acyklicznej strukturze: komórki przed cell na dowolnej ścieżce są mniejsze, więc nie mogą pojawić się po niej, a najlepsza kontynuacja od cell jest taka sama bez względu na to, jak do niej dotarliśmy. Oblicz best dla każdej komórki tylko raz i zapisz wynik, a wykładnicze drzewo przejść zmniejszy się do jednej wizyty na komórkę.

W pierwszym przykładzie 9 nie ma większego sąsiada, więc best wynosi tam 1. Następnie dla 8 wynosi 2, dla 7 wynosi 3, dla 6 i 2 wynosi 4, dla 5 i 1 wynosi 5, dla 4 wynosi 6, a dla 3 wynosi 7 — to jest odpowiedź. Każda komórka sprawdza 4 sąsiadów, więc złożoność wynosi O(m × n).

Naturalnym rozwiązaniem jest kod rekurencyjny: funkcja zwracająca best dla komórki i wywołująca samą siebie dla każdego większego sąsiada. Głębokość wywołań jest równa długości przebytej ścieżki, a ograniczenia dopuszczają ścieżkę przechodzącą przez każdą komórkę: wartości wijące się na przemian w poprzek siatki 100 × 100 tworzą jedną ścieżkę złożoną z 10 000 komórek, podczas gdy Python domyślnie zatrzymuje działanie po 1 000 zagnieżdżonych wywołań. Poniższy kod samodzielnie wykonuje rekurencję, więc żadna ścieżka nie jest dla niego zbyt długa. Przechowuj stos komórek oraz, dla każdej komórki, informację o tym, ile z jej czterech kierunków zostało już sprawdzonych. Sprawdź komórkę na szczycie stosu: jeśli pozostał jej jakiś kierunek, wypróbuj go i umieść tam sąsiada na stosie, jeśli jest większy i nie został jeszcze przetworzony. Gdy sprawdzisz wszystkie cztery kierunki, każdy większy sąsiad będzie już przetworzony, więc zdejmij komórkę ze stosu i ustaw jej best. To dokładnie taka kolejność, w jakiej postępowałoby wywołanie rekurencyjne.

Wyszukiwanie nie wymaga oznaczania komórek jako „w trakcie przetwarzania”, w przeciwieństwie do wykrywania cykli. Każda komórka na stosie jest większa od komórki poniżej niej, więc większy sąsiad komórki na szczycie stosu nie może znajdować się niżej na stosie.

Algorytm

Wypełnij best wartością 0 (jeszcze nieznana) i ustaw licznik kierunków na 0 dla każdej komórki.
Dla każdej komórki, dla której best wynosi 0, umieść ją na stosie.
Spójrz na komórkę na szczycie stosu. Jeśli pozostał jej jakiś kierunek, zwiększ jej licznik i umieść na stosie sąsiada w tym kierunku, jeśli znajduje się on w siatce, ma większą wartość i nie został jeszcze przetworzony.
Jeśli wypróbowano wszystkie cztery kierunki, zdejmij komórkę ze stosu i ustaw best na 1 plus największa wartość best spośród jej sąsiadów o większych wartościach albo na 1, jeśli takich sąsiadów nie ma.
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 answer

Obierz siatkę od jej wierzchołków

Intuicja

Odwróć podejście z programowaniem dynamicznym i buduj rozwiązanie od największych wartości w dół, tak jak algorytm Kahna tworzy porządek topologiczny. Nazwij komórkę szczytem, jeśli żaden z jej sąsiadów nie jest większy. Ścieżka od szczytu nie może się poruszać, więc zawiera 1 komórkę. Usuń jednocześnie wszystkie szczyty: to warstwa 1. Teraz niektóre komórki straciły ostatniego większego sąsiada, więc stają się szczytami pozostałej części. Usuń je jako warstwę 2 i kontynuuj, aż siatka będzie pusta. Odpowiedzią jest liczba warstw.

Dlaczego: komórka trafia do warstwy k dokładnie wtedy, gdy najdłuższa ścieżka zaczynająca się w niej zawiera k komórek. Komórka jest usuwana w rundzie po usunięciu jej ostatniego większego sąsiada, więc jej warstwa jest równa 1 plus najwyższa warstwa spośród jej większych sąsiadów. To ten sam wzór best[cell] = 1 + max(best[nb]) co w poprzednim podejściu. Najgłębsza warstwa odpowiada początkowi najdłuższej ścieżki.

W pierwszym przykładzie jedynym szczytem jest 9 (jej sąsiedzi to 8 i 2). Usunięcie jej uwalnia 8, usunięcie 8 uwalnia 7, usunięcie 7 uwalnia 2 i 6, te dwie komórki uwalniają 1 i 5, 5 uwalnia 4, a 4 uwalnia 3. To 7 warstw, a ścieżka 3, 4, 5, 6, 7, 8, 9 wznosi się przez jedną komórkę z każdej warstwy.

Aby szybko znaleźć następną warstwę, policz dla każdej komórki, ilu większych sąsiadów nadal ma. Usunięcie komórki zmniejsza licznik każdego ściśle mniejszego sąsiada, a gdy licznik osiągnie 0, ten sąsiad trafia do następnej warstwy. Każda komórka jest usuwana raz, a każda para sąsiadów jest sprawdzana stałą liczbę razy, więc złożoność wynosi O(m × n), bez stosu i rekurencji.

Algorytm

Dla każdej komórki policz sąsiadów o większej wartości.
Umieść w bieżącej warstwie każdą komórkę, której licznik wynosi 0.
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ść w następnej warstwie sąsiada, którego licznik osiągnie 0.
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

Błędy wynikają tu ze słowa „ściśle”, głębokiej rekurencji i nawyków przeniesionych z innych zadań z siatkami.

Porównywanie za pomocą >= zamiast >. Przy dwóch sąsiadujących 4 każda z nich jest krokiem w górę względem drugiej, strzałki tworzą pętlę, algorytm brute force chodzi tam i z powrotem w nieskończoność, a memoizowane wyszukiwanie odczytuje długość, która wciąż jest obliczana.
Rekurencja dla bardzo długich ścieżek. Rekurencyjne wyszukiwanie wykonuje tyle zagnieżdżonych wywołań, jak długa jest ścieżka, a ograniczenia dopuszczają ścieżkę przechodzącą przez każdą komórkę: wartości wijące się tam i z powrotem w siatce 100 × 100 tworzą jedną ścieżkę złożoną z 10,000 komórek, czyli dziesięć razy więcej niż domyślny limit Pythona wynoszący 1,000 zagnieżdżonych wywołań. Tak długie ścieżki wymagają wyszukiwania iteracyjnego z własnym stosem albo zwiększenia limitu rekurencji (sys.setrecursionlimit w Pythonie), a bardzo wysoki limit wciąż może przepełnić własny stos interpretera.
Pomijanie już odwiedzonych komórek, tak jak robi to wypełnianie obszaru. Dotarcie do ukończonej komórki nie oznacza ślepego zaułka: zapisana w niej długość jest dokładnie tym, czego potrzebuje bieżąca komórka. Odczytaj ją, nie pomijaj.
Rozpoczynanie wyłącznie od najmniejszej wartości. W pierwszym przykładzie 1 daje 5 komórek, ale odpowiedź, 7, zaczyna się od 3. Najdłuższa ścieżka może zaczynać się w dowolnej komórce, która nie ma mniejszego sąsiada, a takich komórek może być wiele.
Zwracanie 0. Każda komórka jest ścieżką o długości 1, więc siatka o jednakowych wartościach lub siatka 1 × 1 ma odpowiedź 1. Ustaw długość każdej komórki na początku na 1, a nie na 0.
W podejściu polegającym na usuwaniu obniżanie liczby równemu sąsiadowi. Tylko ściśle mniejszy sąsiad stracił większego sąsiada.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu najdłuższej rosnącej ścieżki w macierzy?

Czas O(m × n) i pamięć O(m × n) przy użyciu memoizowanego przeszukiwania w głąb lub topologicznego usuwania. Każda z m × n komórek jest przetwarzana raz i sprawdza swoich 4 sąsiadów stałą liczbę razy, a każda z metod przechowuje jedną liczbę na komórkę. Sprawdzanie każdej ścieżki z każdej komórki jest natomiast wykładnicze: na siatce 100 × 100, gdzie każda wartość jest sumą numeru wiersza i numeru kolumny, z lewego górnego rogu wychodzi ponad 10^58 ścieżek.

Dlaczego ten problem nie wymaga zbioru odwiedzonych węzłów?

Ścieżka, która prowadzi tylko w górę, nigdy nie może wrócić do komórki, ponieważ musiałaby zejść z powrotem do wartości tej komórki. Zasada ścisłego wzrostu już zabrania więc ponownego odwiedzania komórek, a graf kroków nie zawiera cykli. Dlatego zapamiętywanie wyników jest bezpieczne: komórki poprzedzające daną komórkę nie mogą wpływać na ścieżkę za nią.

Czy problem najdłuższej rosnącej ścieżki w macierzy dotyczy programowania dynamicznego czy grafów?

Obie metody. To najdłuższa ścieżka w skierowanym grafie acyklicznym, czyli programowanie dynamiczne według porządku topologicznego: odpowiedź dla komórki to 1 plus najlepsza odpowiedź spośród jej większych sąsiadów. Zapamiętujące wyniki wyszukiwanie w głąb wypełnia tabelę w kolejności, w jakiej wyszukiwanie kończy przetwarzanie komórek, a topologiczne usuwanie wypełnia ją warstwa po warstwie, zaczynając od szczytów. Posortowanie komórek według wartości od największej do najmniejszej daje trzecią poprawną kolejność, kosztem O(m × n × log(m × n)) związanym z sortowaniem.

Czym różni się to od najdłuższego rosnącego podciągu?

Podciąg może pomijać elementy, ale musi zachować ich kolejność, natomiast tutaj ścieżka musi prowadzić do sąsiadującej komórki w jednym z czterech kierunków. Problem podciągu rozwiązuje się za pomocą programowania dynamicznego na linii; ten problem to programowanie dynamiczne na siatce przekształconej w graf. Oba opierają się na tym samym fakcie: ściśle rosnący łańcuch nigdy nie może zawrócić i zapętlić się.

Python

def longestIncreasingPath(matrix):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]

Oczekiwane

Longest Increasing Path in a Matrix

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Podążaj każdą rosnącą ścieżką

Memoizowane przeszukiwanie w głąb z własnym stosem

Obierz siatkę od jej wierzchołków

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania