Trapping Rain Water: stos i dwa wskaźniki
Rozwiązywać problem trapping-rain-water zarówno za pomocą stosu monotonicznego, który oblicza poziome warstwy, jak i metody dwóch wskaźników, która oblicza pionowe kolumny
Trapping Rain Water: stos i dwa wskaźniki to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Problem: zbieranie wody deszczowej
Zbieranie wody deszczowej (LeetCode 42) to jeden z najbardziej znanych problemów pojawiających się podczas rozmów kwalifikacyjnych. Mając n nieujemnych liczb całkowitych reprezentujących mapę wysokości, gdzie każdy słupek ma szerokość 1, należy obliczyć, ile wody może zgromadzić się między słupkami po deszczu. Woda wypełnia każde zagłębienie między wyższymi słupkami po obu stronach.
Dla każdej pozycji i poziom wody wynosi min(max_left[i], max_right[i]) - height[i]. Jeśli wynik jest ujemny, woda się nie gromadzi (słupek jest wyższy niż co najmniej jedna z granic). Istnieją trzy podejścia: wstępnie obliczone tablice O(n)/O(n), dwa wskaźniki O(n)/O(1) oraz monotoniczny stos O(n)/O(n).
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
# Water trapped at each position:
# pos 2: min(1,3)-0=1
# pos 4: min(2,3)-1=1
# pos 5: min(2,3)-0=2
# pos 6: min(2,3)-1=1
# pos 9: min(3,2)-1=1
# Total = 6
print('height:', height)
print('Expected trapped water: 6')
# Visualise
max_h = max(height)
for row in range(max_h, 0, -1):
line = ''
for h in height:
line += '#' if h >= row else ' '
print(line)Podejście 1: wstępnie obliczone tablice maksimów
Proste rozwiązanie o złożoności czasowej O(n) i pamięciowej O(n) wstępnie oblicza dwie tablice: max_left[i] = maksymalna wysokość od indeksu 0 do i oraz max_right[i] = maksymalna wysokość od indeksu i do n-1. Ilość wody na pozycji i wynosi max(0, min(max_left[i], max_right[i]) - height[i]).
Zbudowanie max_left wymaga jednego przebiegu od lewej do prawej, a zbudowanie max_right — jednego przebiegu od prawej do lewej. W ostatnim przebiegu sumuje się ilość wody. To podejście jest przejrzyste i łatwe do wyjaśnienia, ale wymaga dodatkowej pamięci O(n).
def trap_prefix(height):
n = len(height)
if n < 3:
return 0
max_left = [0] * n
max_right = [0] * n
max_left[0] = height[0]
for i in range(1, n):
max_left[i] = max(max_left[i-1], height[i])
max_right[-1] = height[-1]
for i in range(n-2, -1, -1):
max_right[i] = max(max_right[i+1], height[i])
water = 0
for i in range(n):
water += max(0, min(max_left[i], max_right[i]) - height[i])
return water
print(trap_prefix([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_prefix([4,2,0,3,2,5])) # 9Podejście 2: dwa wskaźniki (pamięć O(1))
Podejście z dwoma wskaźnikami osiąga złożoność czasową O(n) i pamięciową O(1). Należy ustawić lewy i prawy wskaźnik na obu końcach tablicy. Wartości max_left i max_right przechowują maksima napotkane dotychczas odpowiednio z lewej i z prawej strony.
W każdym kroku należy przetworzyć stronę z mniejszym bieżącym maksimum — ponieważ to ona wyznacza ograniczenie. Jeśli max_left < max_right, ilość wody dla lewego wskaźnika wynosi max_left - height[left] (prawa strona jest wystarczająco wysoka). Następnie lewy wskaźnik przesuwa się do środka. W przeciwnym razie analogicznie przetwarzana jest prawa strona. Nie są potrzebne wstępnie obliczone tablice.
def trap_two_pointer(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left] # new max on the left
else:
water += max_left - height[left] # trapped by max_left
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap_two_pointer([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_two_pointer([4,2,0,3,2,5])) # 9
print(trap_two_pointer([3,0,3])) # 3Dlaczego działa podejście z dwoma wskaźnikami: niezmiennik
Najważniejsza obserwacja jest następująca: gdy przetwarzamy lewy wskaźnik, ponieważ height[left] < height[right], wiemy, że max_right >= height[right] > height[left]. Zatem rzeczywista prawa granica poziomu wody ma wysokość co najmniej height[right], która już jest większa niż max_left. Dlatego min(max_left, effective_max_right) = max_left, a wzór na ilość wody upraszcza się do max_left - height[left].
Nie musimy znać dokładnej wartości max_right — wystarczy wiedzieć, że jest co najmniej równa height[right] > height[left], aby użyć max_left jako poziomu wody. To elegancki niezmiennik, który umożliwia zastosowanie stałej pamięci O(1).
# Trace two-pointer on [4, 2, 0, 3, 2, 5]
height = [4, 2, 0, 3, 2, 5]
left, right = 0, len(height) - 1
max_l = max_r = water = 0
print('height:', height)
print(f'{'Step':5} {'L':3} {'R':3} {'maxL':5} {'maxR':5} {'water':6} {'total':6}')
step = 0
while left < right:
side = 'L' if height[left] < height[right] else 'R'
if side == 'L':
if height[left] >= max_l: max_l = height[left]
else:
w = max_l - height[left]; water += w
left += 1
else:
if height[right] >= max_r: max_r = height[right]
else:
w = max_r - height[right]; water += w
right -= 1
step += 1
print(f'{step:5} {left:3} {right:3} {max_l:5} {max_r:5} {water:6}')
print('Total trapped:', water)Podejście 3: stos monotoniczny (warstwy poziome)
Podejście ze stosem monotonicznym oblicza ilość wody w poziomych warstwach między sąsiednimi słupkami. Należy utrzymywać monotonicznie malejący stos indeksów. Gdy słupek i jest wyższy niż słupek j na szczycie stosu, powstaje zagłębienie: dno ma wysokość height[j], lewa ściana ma wysokość height[stack[-1]] po usunięciu j, a prawa ściana ma wysokość height[i]. Woda wypełnia zagłębienie do poziomu min(left_wall, right_wall) - floor, a jego szerokość wynosi i - stack[-1] - 1.
Każde „zagłębienie” jest obliczane po napotkaniu wyższego słupka. W ten sposób woda jest przetwarzana w ograniczonych prostokątnych fragmentach, co jest przydatne, gdy trzeba również śledzić, które słupki wpływają na poziom wody.
def trap_stack(height):
stack = [] # monotonic decreasing indices
water = 0
for i in range(len(height)):
while stack and height[stack[-1]] < height[i]:
bottom_idx = stack.pop() # the floor of the valley
if not stack:
break # no left wall, no water
left_idx = stack[-1]
floor = height[bottom_idx]
water_height = min(height[left_idx], height[i]) - floor
width = i - left_idx - 1
water += water_height * width
stack.append(i)
return water
print(trap_stack([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_stack([4,2,0,3,2,5])) # 9Śledzenie działania stosu monotonicznego
Prześledźmy działanie podejścia ze stosem dla [0,1,0,2,1,0,1,3,...]. Gdy napotykamy słupek 3 (h=2) przy i=3, na szczycie stosu znajduje się i=2 (h=0), więc usuwamy ten element. Lewa ściana znajduje się przy i=1 (h=1), a prawa ściana ma wysokość h=2. Wysokość wody = min(1,2)-0=1, szerokość=3-1-1=1, pole=1. Następnie na szczycie stosu znajduje się i=1 (h=1), które nie jest mniejsze od 2, więc kończymy. Umieszczamy 3 na stosie.
Metoda stosowa jest bardziej złożona w implementacji niż metoda dwóch wskaźników, ale pokazuje, które konkretne słupki tworzą poszczególne komórki wody. Ta wiedza jest przydatna w dodatkowych pytaniach dotyczących odtwarzania układu wody lub zliczania odrębnych zagłębień.
def trap_stack_trace(height):
stack = []
water = 0
for i in range(len(height)):
print(f'i={i} h={height[i]}: stack={[height[s] for s in stack]}')
while stack and height[stack[-1]] < height[i]:
bot = stack.pop()
if not stack:
print(f' Pop {height[bot]}: no left wall, skip')
break
left = stack[-1]
h = min(height[left], height[i]) - height[bot]
w = i - left - 1
water += h * w
print(f' Pop {height[bot]}: floor={height[bot]}, left_wall={height[left]}, right_wall={height[i]}, h={h}, w={w}, +{h*w}')
stack.append(i)
return water
result = trap_stack_trace([0,1,0,2,1,0,1,3,2,1,2,1])
print('Total:', result)Porównanie wszystkich trzech podejść
Podsumowanie trzech podejść do problemu zbierania wody deszczowej:
- Tablice prefiksowe: czas O(n), pamięć O(n). Najłatwiejsze do zrozumienia i zweryfikowania. Najlepsze podczas rozmów kwalifikacyjnych, gdy przejrzystość jest ważniejsza niż oszczędność pamięci.
- Dwa wskaźniki: czas O(n), pamięć O(1). Optymalne zarówno pod względem czasu, jak i pamięci. Najlepsze w odpowiedzi na dodatkowe pytanie „czy można użyć O(1) pamięci?”.
- Stos monotoniczny: czas O(n), pamięć O(n). Przetwarza wodę w poziomych warstwach. Najlepszy, gdy trzeba wiedzieć, które słupki wpływają na wynik, lub gdy problem ten pojawia się jako podproblem w większym algorytmie opartym na stosie.
height = [0,1,0,2,1,0,1,3,2,1,2,1]
# All three methods — verify they agree
def trap_prefix(h):
n = len(h)
ml = [0]*n; mr = [0]*n; ml[0]=h[0]; mr[-1]=h[-1]
for i in range(1,n): ml[i]=max(ml[i-1],h[i])
for i in range(n-2,-1,-1): mr[i]=max(mr[i+1],h[i])
return sum(max(0,min(ml[i],mr[i])-h[i]) for i in range(n))
def trap_two_ptr(h):
l,r,ml,mr,w = 0,len(h)-1,0,0,0
while l<r:
if h[l]<h[r]:
ml=max(ml,h[l]); w+=ml-h[l]; l+=1
else:
mr=max(mr,h[r]); w+=mr-h[r]; r-=1
return w
def trap_stk(h):
stk,w = [],[]
for i in range(len(h)):
while stk and h[stk[-1]]<h[i]:
b=stk.pop()
if not stk: break
w.append(max(0,min(h[stk[-1]],h[i])-h[b])*(i-stk[-1]-1))
stk.append(i)
return sum(w)
for h in [height, [4,2,0,3,2,5], [3,0,3], [1,0,1]]:
p=trap_prefix(h); t=trap_two_ptr(h); s=trap_stk(h)
print(f'{h}: prefix={p}, two-ptr={t}, stack={s}, match={p==t==s}')Pojemnik z największą ilością wody
Pojemnik z największą ilością wody (LeetCode 11) jest często mylony z problemem zbierania wody deszczowej. W tym przypadku wybierają Państwo dokładnie dwa słupki, a wodę ograniczają wyłącznie te dwa słupki — wewnętrzne słupki nie mają znaczenia. Należy zmaksymalizować pole min(height[l], height[r]) × (r - l).
Dwa wskaźniki rozwiązują ten problem zachłannie: zaczynamy na obu końcach (od maksymalnej szerokości). Krótszy wskaźnik przesuwamy do środka — przesunięcie wyższego może tylko zmniejszyć pole. Złożoność wynosi O(n) czasowo i O(1) pamięciowo, a rozwiązanie jest prostsze niż metoda dwóch wskaźników dla problemu zbierania wody deszczowej, ponieważ nie trzeba przechowywać bieżącego maksimum.
def max_water_container(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
# Move the shorter bar: moving taller bar can only reduce min
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
print(max_water_container([1,8,6,2,5,4,8,3,7])) # 49: bars 8 and 7
print(max_water_container([1,1])) # 1
print(max_water_container([4,3,2,1,4])) # 16
# Key difference from trapping rain water:
# Container: choose 2 bars, water fills freely between them (no internal barriers)
# Trapping: water fills ALL valleys in the full elevation mapZaawansowane: Zbieranie wody deszczowej II (3D)
Zbieranie wody deszczowej II (LeetCode 407) rozszerza problem na dwuwymiarową macierz wysokości. Woda może płynąć we wszystkich czterech kierunkach i musi wypływać przez krawędź. Rozwiązanie wykorzystuje kopiec minimum: najpierw umieszczamy w kopcu wszystkie komórki brzegowe, a następnie wykonujemy ekspansję podobną do BFS. Przetwarzamy komórkę o najmniejszej wysokości — każdy niższy sąsiad musi pomieścić wodę co najmniej na poziomie bieżącej komórki.
Jest to zasadniczo inny algorytm niż w przypadku jednowymiarowym i sprawdza zarówno operacje na kopcu, jak i przechodzenie metodą BFS. Sztuczka z dwoma wskaźnikami dla przypadku 1D nie uogólnia się na 2D, natomiast podejście z kopcem — tak.
import heapq
def trap_rain_water_2d(heightMap):
if not heightMap or not heightMap[0]:
return 0
m, n = len(heightMap), len(heightMap[0])
visited = [[False]*n for _ in range(m)]
heap = [] # (height, row, col)
# Add all border cells to the heap
for i in range(m):
for j in [0, n-1]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
for j in range(n):
for i in [0, m-1]:
if not visited[i][j]:
heapq.heappush(heap, (heightMap[i][j], i, j))
visited[i][j] = True
total = 0
max_h = 0
while heap:
h, r, c = heapq.heappop(heap)
max_h = max(max_h, h)
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0<=nr<m and 0<=nc<n and not visited[nr][nc]:
visited[nr][nc] = True
total += max(0, max_h - heightMap[nr][nc])
heapq.heappush(heap, (max(max_h, heightMap[nr][nc]), nr, nc))
return total
map2d = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
print(trap_rain_water_2d(map2d)) # 4Kiedy stosować poszczególne metody podczas rozmów kwalifikacyjnych
Poradnik wyboru metody podczas rozmowy kwalifikacyjnej dotyczącej zbierania wody deszczowej:
- Na początek: tablice prefiksowe — łatwe do wyjaśnienia, intuicyjne wizualnie i jednoznacznie poprawne
- Dodatkowe pytanie „O(1) pamięci?”: dwa wskaźniki — należy wyjaśnić niezmiennik, zgodnie z którym niższa strona stanowi wąskie gardło
- Jeśli osoba prowadząca rozmowę zapyta „czy istnieje inne podejście?”: stos monotoniczny — należy wyjaśnić obliczanie warstw poziomych
Przed przejściem do kodu należy zawsze jasno określić, co wyznacza poziom wody w każdej pozycji — minimum z najwyższych słupków po obu stronach. Pokazuje to zrozumienie problemu i ułatwia wyjaśnienie rozwiązania.
# Quick summary of all three approaches
approaches = [
{
'name': 'Prefix max arrays',
'time': 'O(n)', 'space': 'O(n)',
'description': '3 passes: build max_left, max_right, sum water column-by-column',
},
{
'name': 'Two pointers',
'time': 'O(n)', 'space': 'O(1)',
'description': 'Process smaller side: its max is the limiting wall, no array needed',
},
{
'name': 'Monotonic stack',
'time': 'O(n)', 'space': 'O(n)',
'description': 'Compute water in horizontal layers when a taller bar is encountered',
},
]
for a in approaches:
print(f'{a["name"]} [{a["time"]} / {a["space"]}]')
print(f' {a["description"]}')
print()Przypadki brzegowe i typowe błędy
Typowe błędy w problemie zbierania wody deszczowej:
- Pomijanie min: poziom wody wynosi
min(max_left, max_right), a nie tylko jedną z tych wartości. Słupek potrzebuje wysokich ścian po obu stronach. - Ujemna ilość wody: należy użyć
max(0, ...), aby ograniczyć wartości ujemne do 0, gdy wysokość słupka przekracza poziom wody. - Pozycje skrajne: skrajny lewy i skrajny prawy słupek nigdy nie mogą zatrzymywać wody, ponieważ po jednej stronie nie mają ściany. Podejście z tablicami prefiksowymi obsługuje to naturalnie, ponieważ
max_left[0] = height[0]sprawia, że ilość wody w indeksie 0 zawsze wynosi 0. - Puste lub bardzo małe tablice: dla tablic zawierających mniej niż 3 elementy należy zwrócić 0.
def trap(height):
n = len(height)
if n < 3:
return 0 # need at least 3 bars to trap anything
left, right = 0, n - 1
max_l = max_r = water = 0
while left < right:
if height[left] <= height[right]:
if height[left] >= max_l:
max_l = height[left]
else:
water += max_l - height[left] # never negative: max_l > height[left]
left += 1
else:
if height[right] >= max_r:
max_r = height[right]
else:
water += max_r - height[right]
right -= 1
return water
# Edge cases
print(trap([])) # 0: empty
print(trap([1])) # 0: single bar
print(trap([1,2])) # 0: two bars
print(trap([3,0,3])) # 3: simple valley
print(trap([3,3,3])) # 0: flat top, no waterSzybkie sprawdzenie
Sprawdź swoją znajomość koncepcji Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo następujące zagadnienia: problem zbierania wody deszczowej rozwiązuje się, znajdując w każdej pozycji minimum z najwyższych ścian po lewej i prawej stronie, podejście z dwoma wskaźnikami i pamięcią O(1) działa, ponieważ bieżące maksimum po stronie niższej jest zawsze ograniczeniem decydującym, a podejście ze stosem monotonicznym oblicza wodę w warstwach poziomych, dzięki czemu jest przydatne w połączeniu z inną logiką opartą na stosie. Następnie przejdziemy do zagadnień związanych z projektowaniem systemów, zaczynając od frameworka RADIO, który służy do udzielania uporządkowanych odpowiedzi podczas rozmów kwalifikacyjnych.
Ucz się Python dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 30
- Lekcje
- 120
Często zadawane pytania
Czy lekcja „Trapping Rain Water: stos i dwa wskaźniki” jest bezpłatna?
Tak — pełny tekst „Trapping Rain Water: stos i dwa wskaźniki” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Trapping Rain Water: stos i dwa wskaźniki”?
Rozwiązywać problem trapping-rain-water zarówno za pomocą stosu monotonicznego, który oblicza poziome warstwy, jak i metody dwóch wskaźników, która oblicza pionowe kolumny Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Trapping Rain Water: stos i dwa wskaźniki”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Stos monotoniczny: rosnący a malejący
- Największy prostokąt w histogramie
- Maksimum w oknie przesuwnym za pomocą monotonicznej kolejki dwustronnej
- Trapping Rain Water: stos i dwa wskaźniki