Trapping Rain Water

Q: Jaka jest złożoność czasowa problemu z zatrzymywaniem wody deszczowej?

Rozwiązanie z dwoma wskaźnikami działa w czasie O(n) i wymaga O(1) dodatkowej pamięci: w każdym kroku jeden wskaźnik przesuwa się do środka, więc jest n-1 kroków. Wersja z tablicami leftMax i rightMax również działa w czasie O(n) , ale wymaga O(n) pamięci. Skanowanie obu stron od każdego słupka wymaga O(n²) , czyli około 4 × 10^8 odczytów dla 2 × 10^4 słupków.

Q: Dlaczego rozwiązanie z dwoma wskaźnikami może przesuwać krótszy bok?

Każdy wcześniej minięty słupek nie jest wyższy niż wyższy z dwóch aktualnych słupków, ponieważ przesuwa się tylko niższy wskaźnik. Gdy więc lewy słupek jest niższy, jego dotychczasowe maksimum jest nie większe niż wysokość prawego słupka, a prawy słupek stanowi rzeczywistą ścianę po jego prawej stronie. Poziom przy lewym wskaźniku odpowiada jego dotychczasowemu maksimum, niezależnie od tego, co znajduje się między wskaźnikami, więc możesz rozliczyć ten słupek i przejść dalej.

Q: Czy problem „Trapping Rain Water” można rozwiązać za pomocą stosu?

Tak. Przechowuj indeksy słupków na stosie, w kolejności rosnącej wysokości od dołu do góry. Gdy pojawi się słupek wyższy od tego na szczycie stosu, zdejmij go ze stosu: jego wysokość jest dnem niecki, której ścianami są nowy szczyt stosu i bieżący słupek. Dodaj (min(two walls) - floor) × (distance between the walls - 1) i zdejmuj słupki ze stosu, dopóki bieżący słupek jest wyższy. Stos wypełnia wodę poziomymi warstwami zamiast kolumnami, w czasie O(n) i przy użyciu O(n) pamięci.

Q: Czym różni się zadanie Trapping Rain Water od zadania Container With Most Water?

W zadaniu Container With Most Water wybierasz dwie linie, a linie między nimi nie zajmują miejsca, więc odpowiedzią jest jeden prostokąt — największy z nich. Tutaj każdy słupek jest pełny, woda znajduje się na każdym słupku, a odpowiedzią jest suma dla wszystkich słupków. W obu przypadkach używa się dwóch wskaźników, które przesuwają niższą stronę, z tego samego powodu: niższa strona to ta, której wynik jest już przesądzony.

TrudneDwa wskaźniki Stos monotoniczny

+10

Rząd słupków stoi obok siebie, każdy o szerokości jednej jednostki: height[i] to wysokość słupka i. Na rząd pada deszcz, a woda gromadzi się w zagłębieniach między słupkami. Woda utrzymuje się nad słupkiem tylko wtedy, gdy gdzieś po jego lewej i prawej stronie stoi wyższy słupek; za pierwszym i ostatnim słupkiem spływa.

Zwróć łączną liczbę jednostkowych kwadratów wody, które zatrzymują się w tym rzędzie.

Funkcja

trap(height: integer-array) → integer

heightinteger-array: wysokość każdego słupka, od lewej do prawej
Zwracainteger: łączna liczba jednostek uwięzionej wody

Ograniczenia

1 ≤ height.length ≤ 2 × 10⁴
0 ≤ height[i] ≤ 10⁵
Każdy słupek ma szerokość jednej jednostki, a woda nie utrzymuje się poza pierwszym ani ostatnim słupkiem.

Przykłady

Wejście: height = [0, 3, 1, 0, 2, 5, 1, 2]
Wyjście: 7
Wyjaśnienie: Między 3 a 5 poziom wody wzrasta do 3: zatrzymują ją 2 jednostki nad słupkiem o wysokości 1, 3 nad słupkiem o wysokości 0 i 1 nad słupkiem o wysokości 2. 1 pod koniec znajduje się między 5 a 2, więc poziom wody wynosi 2 i zatrzymuje się 1 jednostka. 2 + 3 + 1 + 1 = 7.

+17 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Załóżmy, że słupki tworzą dwuwymiarową siatkę wysokości, a woda może uciekać we wszystkich czterech kierunkach. Jak policzysz wtedy uwięzioną wodę?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Poziom wody nad każdym słupkiem zależy od słupków, które mogą znajdować się daleko po obu stronach, więc lokalne sprawdzanie sąsiadów daje błędny wynik. Rozwiązaniem jest jeden wzór: poziom nad słupkiem to mniejsza z wartości najwyższego słupka po jego lewej i najwyższego słupka po jego prawej stronie. Wyszukiwanie tych dwóch maksimów dla każdego słupka jest powolne, zapisanie ich w dwóch tablicach sprawia, że algorytm działa w czasie liniowym, a dwa wskaźniki, które zawsze przesuwają się po niższej stronie, w ogóle nie wymagają tablic.

Skanuj oba końce każdego taktu

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

Intuicja

Zliczaj wodę kolumna po kolumnie. Woda nad słupkiem i wznosi się, aż przelałaby się przez niższą z dwóch ścian. Lewa ściana to najwyższy słupek na odcinku od indeksu 0 do i; prawa ściana to najwyższy słupek na odcinku od i do końca. Zatem poziom wody wynosi min(leftMax, rightMax), a ilość wody nad słupkiem i to ten poziom minus height[i].

Weźmy [0, 3, 1, 0, 2, 5, 1, 2] i słupek o wysokości 0 na indeksie 3. Najwyższy słupek po jego lewej stronie ma wysokość 3, a po prawej — 5. Poziom wody wynosi 3, więc znajduje się tam 3 jednostki wody. W przypadku słupka o wysokości 1 na indeksie 6 ściany mają wysokość 5 i 2: poziom wynosi 2, a słupek zatrzymuje 1 jednostkę wody.

Oba skanowania uwzględniają sam słupek i. Dzięki temu wynik nie jest ujemny: gdy słupek i jest wyższy niż wszystkie słupki po jednej stronie, maksimum po tej stronie jest równe jego własnej wysokości, poziom wody jest jej równy, a słupek zatrzymuje 0 jednostek wody. Dlatego też pierwszy i ostatni słupek zawsze zatrzymują 0 jednostek wody.

Problemem jest koszt. Dla każdego słupka przeglądamy cały rząd — połowę po lewej i połowę po prawej — więc łącznie wykonujemy n × n odczytów: 4 × 10^8 dla 2 × 10^4 słupków. Skanowania powtarzają też tę samą pracę: najwyższy słupek na lewo od indeksu 5 to najwyższy słupek na lewo od indeksu 4 plus jedno dodatkowe porównanie, a algorytm siłowy oblicza tę wartość od zera.

Algorytm

Ustaw water na 0.
Dla każdego indeksu i przeskanuj elementy od 0 do i, aby znaleźć leftMax.
Przeskanuj elementy od i do ostatniego indeksu, aby znaleźć rightMax.
Dodaj min(leftMax, rightMax) - height[i] do water.
Zwróć water.

def trap(height):
    n = len(height)
    water = 0
    for i in range(n):
        # The tallest bar at or left of i, and the tallest at or right of i.
        left_max = 0
        for j in range(i + 1):
            left_max = max(left_max, height[j])
        right_max = 0
        for j in range(i, n):
            right_max = max(right_max, height[j])
        water += min(left_max, right_max) - height[i]
    return water

Wstępnie oblicz najwyższy słupek po każdej stronie

Intuicja

Wzór pozostaje ten sam; zmienia się tylko sposób wyznaczania dwóch ścian. Najwyższy słupek od 0 do i to większa z wartości: najwyższy słupek od 0 do i-1 oraz height[i]. Jedno przejście od lewej do prawej wypełnia tablicę leftMax, a każdy jej element jest wyznaczany na podstawie poprzedniego. Jedno przejście od prawej do lewej wypełnia w ten sam sposób rightMax. Trzecie przejście dodaje min(leftMax[i], rightMax[i]) - height[i] dla każdego słupka.

Dla [0, 3, 1, 0, 2, 5, 1, 2]: leftMax = [0, 3, 3, 3, 3, 5, 5, 5] i rightMax = [5, 5, 5, 5, 5, 5, 2, 2]. Mniejsze z odpowiadających sobie wartości to poziomy [0, 3, 3, 3, 3, 5, 2, 2]. Odejmij wysokości, a otrzymasz [0, 0, 2, 3, 1, 0, 1, 0], których suma wynosi 7.

Każde przejście odwiedza każdy słupek raz, więc złożoność czasowa wynosi O(n): około 6 × 10^4 kroków dla 2 × 10^4 słupków zamiast 4 × 10^8. Kosztem są dwie dodatkowe tablice zawierające po n liczb. To od tego rozwiązania warto zacząć na rozmowie kwalifikacyjnej: trudno popełnić w nim błąd, a następne podejście pozwala pozbyć się tablic, nie zmieniając samej idei.

Algorytm

Wypełnij leftMax od lewej do prawej: leftMax[0] = height[0], a następnie leftMax[i] = max(leftMax[i-1], height[i]).
Wypełnij rightMax od prawej do lewej: rightMax[n-1] = height[n-1], a następnie rightMax[i] = max(rightMax[i+1], height[i]).
Dla każdego indeksu dodaj min(leftMax[i], rightMax[i]) - height[i] do sumy.
Zwróć sumę.

def trap(height):
    n = len(height)
    left_max = [0] * n   # tallest bar from index 0 to i
    right_max = [0] * n  # tallest bar from index i to n-1
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    return water

Dwa wskaźniki przesuwające dolną stronę

Intuicja

Wzór wymaga tylko niższej z dwóch ścian. Jeśli możesz udowodnić, że lewa ściana jest niższa przy danym indeksie, w ogóle nie potrzebujesz prawej ściany dla tego indeksu. Dwa wskaźniki pozwalają to udowodnić. Ustaw left na indeksie 0, a right na ostatnim indeksie, i przechowuj leftMax oraz rightMax — najwyższe słupki, które minął dotąd każdy wskaźnik, wliczając słupek, na którym aktualnie się znajduje.

Niezmiennik: każdy słupek, który wskaźniki już minęły, nie jest wyższy od wyższego z dwóch słupków, na których teraz stoją. Jest spełniony, ponieważ zawsze przesuwasz wskaźnik znajdujący się przy niższym słupku, więc wskaźnik mija tylko słupek, który nie jest wyższy od słupka pod drugim wskaźnikiem.

Załóżmy teraz, że height[left] < height[right]. Z niezmiennika wynika, że leftMax jest co najwyżej równe height[right], a height[right] to sam słupek znajdujący się na prawo od left. Prawa ściana dla left jest więc co najmniej tak wysoka jak leftMax, a poziom w miejscu left jest dokładnie równy leftMax, niezależnie od tego, co znajduje się między wskaźnikami. Dodaj leftMax - height[left] i przesuń left o jeden krok w prawo. Gdy height[right] jest niższym lub równie wysokim słupkiem, wykonaj analogiczne działania po prawej stronie. Zaktualizuj bieżące maksimum przed dodaniem wody, aby słupek pod wskaźnikiem liczył się jako jego własna ściana, a ilość wody nigdy nie była ujemna.

Prześledźmy [0, 3, 1, 0, 2, 5, 1, 2]. Wskaźniki zaczynają na 0 i 2: lewy słupek jest niższy, mieści 0 wody. Następnie 3 kontra 2: prawy słupek jest niższy, rightMax przyjmuje wartość 2, mieści on 0 wody. Potem 3 kontra 1: prawy słupek znów jest niższy, słupek o wysokości 1 mieści 2-1 = 1 jednostkę wody. Następnie 3 kontra 5: teraz lewy słupek jest niższy, leftMax wynosi 3; słupek o wysokości 3 mieści 0, ten o wysokości 1 mieści 2, ten o wysokości 0 mieści 3, a ten o wysokości 2 mieści 1 jednostkę wody. Wskaźniki spotykają się przy słupku o wysokości 5. Łącznie to 1 + 2 + 3 + 1 = 7, przy jednym przejściu i czterech zmiennych.

Algorytm

Ustaw left = 0, right = n-1 oraz leftMax, rightMax i water na 0.
Gdy left < right, porównaj height[left] z height[right].
Jeśli lewy słupek jest niższy, w razie potrzeby zwiększ leftMax do wartości height[left], dodaj leftMax - height[left] i przesuń left w prawo.
W przeciwnym razie w razie potrzeby zwiększ rightMax do wartości height[right], dodaj rightMax - height[right] i przesuń right w lewo.
Zwróć water, gdy wskaźniki się spotkają; słupek, na którym się spotkają, jest najwyższy i niczego nie zatrzymuje.

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0  # tallest bar passed so far from each end
    water = 0
    while left < right:
        if height[left] < height[right]:
            # A bar taller than height[left] waits on the right, so left_max sets the level here.
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            # A bar at least as tall as height[right] waits on the left, so right_max sets the level.
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

Pułapki i przypadki brzegowe

Wzór jest krótki, a większość błędnych odpowiedzi wynika z nieprawidłowej kolejności dwóch wierszy albo z tego, który wskaźnik przesuwasz.

Dodawanie wody przed aktualizacją bieżącego maksimum. Jeśli height[left] jest większe niż leftMax, leftMax - height[left] jest ujemne i suma maleje. Najpierw zwiększ maksimum, a potem dodaj.
Przesuwanie wskaźnika przy wyższym słupku. Poziom jest znany tylko po niższej stronie; przesuwając wyższą stronę, opierasz się na ścianie, której nie udało Ci się potwierdzić. Dla [4, 1, 3, 0, 5] ta wersja zwraca 4 zamiast 8.
Sprawdzanie tylko najbliższych sąsiadów. Ściany ograniczające słupek mogą być daleko: w [3, 0, 2, 0, 1, 0, 4] słupek o wysokości 1 zatrzymuje wodę do poziomu 3, wyznaczonego przez słupki oddalone o cztery i dwa kroki. Odpowiedź wynosi tam 12.
Traktowanie skrajnych elementów tablicy jak ścian. Woda za pierwszym lub ostatnim słupkiem odpływa, więc pojedynczy słupek, dwa słupki albo rząd, który tylko rośnie lub tylko maleje, zatrzymuje 0 jednostek wody.
Pomijanie słupka i w jego własnych skanach w rozwiązaniu brute force. Wtedy słupek wyższy od obu stron otrzymuje ujemną wartość. Uwzględnij go albo ogranicz wynik do minimum 0.
Przepełnienie w wariancie, który mnoży. Tutaj odpowiedź osiąga około 2 × 10^9 (dwa słupki o wysokości 10^5 otaczające 19,998 pustych komórek), co nadal mieści się w 32-bitowej liczbie całkowitej ze znakiem; we własnych wariantach używaj sum 64-bitowych.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu z zatrzymywaniem wody deszczowej?

Rozwiązanie z dwoma wskaźnikami działa w czasie O(n) i wymaga O(1) dodatkowej pamięci: w każdym kroku jeden wskaźnik przesuwa się do środka, więc jest n-1 kroków. Wersja z tablicami leftMax i rightMax również działa w czasie O(n), ale wymaga O(n) pamięci. Skanowanie obu stron od każdego słupka wymaga O(n²), czyli około 4 × 10^8 odczytów dla 2 × 10^4 słupków.

Dlaczego rozwiązanie z dwoma wskaźnikami może przesuwać krótszy bok?

Każdy wcześniej minięty słupek nie jest wyższy niż wyższy z dwóch aktualnych słupków, ponieważ przesuwa się tylko niższy wskaźnik. Gdy więc lewy słupek jest niższy, jego dotychczasowe maksimum jest nie większe niż wysokość prawego słupka, a prawy słupek stanowi rzeczywistą ścianę po jego prawej stronie. Poziom przy lewym wskaźniku odpowiada jego dotychczasowemu maksimum, niezależnie od tego, co znajduje się między wskaźnikami, więc możesz rozliczyć ten słupek i przejść dalej.

Czy problem „Trapping Rain Water” można rozwiązać za pomocą stosu?

Tak. Przechowuj indeksy słupków na stosie, w kolejności rosnącej wysokości od dołu do góry. Gdy pojawi się słupek wyższy od tego na szczycie stosu, zdejmij go ze stosu: jego wysokość jest dnem niecki, której ścianami są nowy szczyt stosu i bieżący słupek. Dodaj (min(two walls) - floor) × (distance between the walls - 1) i zdejmuj słupki ze stosu, dopóki bieżący słupek jest wyższy. Stos wypełnia wodę poziomymi warstwami zamiast kolumnami, w czasie O(n) i przy użyciu O(n) pamięci.

Czym różni się zadanie Trapping Rain Water od zadania Container With Most Water?

W zadaniu Container With Most Water wybierasz dwie linie, a linie między nimi nie zajmują miejsca, więc odpowiedzią jest jeden prostokąt — największy z nich. Tutaj każdy słupek jest pełny, woda znajduje się na każdym słupku, a odpowiedzią jest suma dla wszystkich słupków. W obu przypadkach używa się dwóch wskaźników, które przesuwają niższą stronę, z tego samego powodu: niższa strona to ta, której wynik jest już przesądzony.