Trapping Rain Water
Rząd słupków stoi obok siebie, każdy o szerokości jednej jednostki: height[i] to wysokość słupka i. Woda deszczowa 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 znajduje się wyższy słupek; za pierwszym i ostatnim słupkiem spływa. Zwróć łączną liczbę jednostek wody, którą zatrzymuje rząd.
Funkcja
- heightinteger-array
- wysokość każdego słupka, od lewej do prawej
- Zwracainteger
- łączna liczba jednostek uwięzionej wody
Ograniczenia
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- Każdy słupek ma szerokość jednej jednostki, a woda nie utrzymuje się za pierwszym ani za 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 wynosi 3: 2 jednostki ponad 1, 3 ponad 0, 1 ponad 2. Późniejsze 1 znajduje się między 5 a 2, więc zachowuje wartość 1. To daje 7.
- Wejście
- height = [4, 1, 3, 0, 5]
- Wyjście
- 8
- Wyjaśnienie
- Niższa ściana ma wysokość 4, więc zagłębienie napełnia się do poziomu 4: 3 jednostki nad 1, 1 nad 3, 4 nad 0, co daje 8. Woda przelewa się przez 4, zanim 5 zacznie mieć znaczenie.
- Wejście
- height = [1, 2, 4, 2, 1]
- Wyjście
- 0
- Wyjaśnienie
- Słupki wznoszą się do 4 i znów opadają. Każdy słupek ma stronę, za którą nic nie jest wyższe, więc woda odpływa, a odpowiedź wynosi 0.
Pytanie dodatkowe
Załóżmy, że słupki tworzą dwuwymiarową siatkę wysokości, a woda może uciekać we wszystkich czterech kierunkach. Jak policzyć wtedy uwięzioną wodę?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Zapomnij o całym wierszu i przyjrzyj się jednemu słupkowi. Jak wysoko może sięgać woda ponad słupek
ii które słupki decydują o tej wysokości?Poziom wody nad słupkiem
ijest mniejszą z dwóch wartości: wysokości najwyższego słupka od początku doioraz wysokości najwyższego słupka odido końca. Słupekimieści wodę na poziomie równym tej wartości pomniejszonej o jego własną wysokość. Obie maksymalne wartości można wyznaczyć podczas jednego przejścia od każdego z końców.Potrzebujesz tylko mniejszej z tych dwóch wartości maksymalnych. Ustaw po jednym wskaźniku na każdym końcu i zapamiętuj najwyższy słupek, który minął każdy ze wskaźników. Poziom wody przy wskaźniku stojącym przy niższym słupku wyznacza jego dotychczasowe maksimum: dodaj tę ilość wody i przesuń ten wskaźnik do środka. Zatrzymaj się, gdy wskaźniki się spotkają.
Rozwiązanie
Ilość wody nad słupkiem zależy od słupków, które mogą znajdować się daleko po obu jego stronach. Jej poziom to mniejsza z wysokości najwyższego słupka po jego lewej stronie i najwyższego słupka po jego prawej stronie, a słupek zatrzymuje wodę do tego poziomu pomniejszonego o jego własną wysokość. Podejścia różnią się tylko sposobem wyznaczania tych dwóch maksimów.
Przeskanuj obie strony każdego słupka
Poprawne, ale nie kończy się na największych testach
Intuicja
Dla każdego słupka i przeszukaj zakres od 0 do i, aby znaleźć najwyższy słupek po lewej, a następnie zakres od i do końca, aby znaleźć najwyższy po prawej, po czym dodaj min(leftMax, rightMax) - height[i]. Uwzględnienie słupka i w obu przeszukiwaniach zapobiega uzyskaniu ujemnej wartości i daje 0 dla skrajnych słupków.
Każdy słupek przegląda cały wiersz: n = 2 × 10^4 oznacza 4 × 10^8 odczytów, z których większość powtarza przeszukiwanie wykonane dla poprzedniego słupka.
Algorytm
- Ustaw
waterna 0. - Dla każdego indeksu
iskanuj od 0 doi, aby znaleźćleftMax. - Skanuj od
ido ostatniego indeksu, aby znaleźćrightMax. - Dodaj
min(leftMax, rightMax) - height[i]dowater. - 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 waterWstępnie oblicz najwyższy słupek po każdej stronie
Intuicja
Najwyższy słupek od 0 do i jest większy z najwyższego słupka od 0 do i-1 oraz height[i]. Dlatego jedno przejście od lewej wypełnia leftMax, przy czym każdy element jest tworzony na podstawie poprzedniego, a jedno przejście od prawej wypełnia rightMax. Trzecie przejście stosuje wzór.
Dla [0, 3, 1, 0, 2, 5, 1, 2] poziomy min(leftMax[i], rightMax[i]) wynoszą [0, 3, 3, 3, 3, 5, 2, 2]. Po odjęciu wysokości otrzymujemy [0, 0, 2, 3, 1, 0, 1, 0], co sumuje się do 7. Złożoność czasowa wynosi O(n), kosztem dwóch tablic po n liczb.
Algorytm
- Wypełnij
leftMaxod lewej do prawej:leftMax[0] = height[0], a następnieleftMax[i] = max(leftMax[i-1], height[i]). - Wypełnij
rightMaxod prawej do lewej:rightMax[n-1] = height[n-1], a następnierightMax[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 waterDwa wskaźniki przesuwające niższą stronę
Intuicja
Wzór wymaga tylko niższej ściany, a dwa wskaźniki pozwalają ustalić, która to jest. Ustaw left na 0, a right na ostatnim indeksie; śledź leftMax i rightMax — najwyższe słupki, które minął każdy wskaźnik, łącznie ze słupkiem, na którym się znajduje — i zawsze przesuwaj wskaźnik przy niższym słupku. Wtedy żaden z już miniętych słupków nie jest wyższy od wyższego z dwóch bieżących słupków, ponieważ wskaźnik przesuwa się za słupek tylko wtedy, gdy nie jest on wyższy od słupka pod drugim wskaźnikiem.
Załóżmy, że height[left] < height[right]. Z niezmiennika wynika, że leftMax jest nie większe niż height[right], czyli słupek po prawej stronie od left. Prawa ściana dla left ma więc wysokość co najmniej równą leftMax, a poziom wody wynosi dokładnie leftMax — niezależnie od tego, co znajduje się między wskaźnikami. Gdy prawy słupek jest niższy lub równie wysoki, lustrzany argument rozstrzyga sytuację dla right.
Algorytm
- Ustaw
left = 0,right = n-1orazleftMax,rightMaxiwaterna 0. - Gdy
left < right: jeśliheight[left] < height[right], w razie potrzeby zwiększleftMaxdo wartościheight[left], dodajleftMax - height[left]i przesuńleftw prawo. - W przeciwnym razie zrób to samo po prawej stronie i przesuń
rightw lewo. - Zwróć
water. Słupek, przy którym spotykają się wskaźniki, 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
- Dodawanie wody przed zaktualizowaniem bieżącego maksimum. Gdy
height[left]jest większe niżleftMax, ilość jest ujemna i suma się zmniejsza. - Przesuwanie wskaźnika przy wyższym słupku, którego poziom nie jest potwierdzony. Dla
[4, 1, 3, 0, 5]ta wersja zwraca 4 zamiast 8. - Uwzględnianie tylko najbliższych sąsiadów. W
[3, 0, 2, 0, 1, 0, 4]słupek o wysokości 1 wypełnia się do poziomu 3, wyznaczonego przez słupki oddalone o cztery i dwa kroki; odpowiedź wynosi 12. - Traktowanie końców tablicy jak ścian. Woda tam spływa, więc jeden słupek, dwa słupki lub rząd, który tylko rośnie albo tylko maleje, zatrzymuje 0 jednostek wody.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu zatrzymywania wody deszczowej?
Rozwiązanie z dwoma wskaźnikami działa w czasie O(n) i wymaga O(1) dodatkowego miejsca, ponieważ w każdym kroku jeden ze wskaźników przesuwa się do środka. Wersja z tablicami leftMax i rightMax również działa w czasie O(n), ale wymaga O(n) miejsca. Skanowanie obu stron od każdego słupka ma złożoność O(n²).
Czy problem zbierania wody deszczowej można rozwiązać za pomocą stosu?
Tak. Przechowuj stos indeksów, na których wysokości słupków maleją. Gdy pojawi się wyższy słupek, zdejmij element ze szczytu: to dno basenu ograniczonego nowym szczytem stosu i bieżącym słupkiem. Dodaj (min(two walls) - floor) × (distance between the walls - 1) i zdejmuj kolejne elementy. W ten sposób wypełnisz wodę poziomymi warstwami, w czasie i złożoności pamięciowej O(n).
Czym różni się Trapping Rain Water od Container With Most Water?
W zadaniu Container With Most Water linie nie zajmują miejsca, a odpowiedzią jest największy prostokąt między dwiema liniami. Tutaj każdy słupek jest pełny, a odpowiedź to suma wody nad wszystkimi słupkami. W obu przypadkach przesuwamy niższy bok z tego samego powodu: jego wynik jest już przesądzony.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def trap(height):
# Napisz kod tutajTest #1
Test #2
Test #3
Argument
height = [0, 3, 1, 0, 2, 5, 1, 2]
Oczekiwany wynik
7