Trapping Rain Water: Stack und Zwei-Zeiger
Lösen Sie trapping-rain-water sowohl mit dem monotonen Stack, der horizontale Schichten berechnet, als auch mit dem Zwei-Zeiger-Ansatz, der vertikale Säulen berechnet.
Trapping Rain Water: Stack und Zwei-Zeiger ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Problem: Regenwasser auffangen
Regenwasser auffangen (LeetCode 42) ist eines der bekanntesten Probleme aus Vorstellungsgesprächen. Gegeben sind n nichtnegative Ganzzahlen, die eine Höhenkarte darstellen, wobei jeder Balken die Breite 1 hat. Berechnen Sie, wie viel Wasser sich nach dem Regen zwischen den Balken sammeln kann. Wasser sammelt sich in jedem Tal zwischen höheren Balken auf beiden Seiten.
Für jede Position i lautet der Wasserstand min(max_left[i], max_right[i]) - height[i]. Ist dieser Wert negativ, wird kein Wasser aufgefangen (der Balken ist höher als mindestens eine Begrenzung). Es gibt drei Ansätze: vorab berechnete Arrays mit O(n)/O(n), zwei Zeiger mit O(n)/O(1) und ein monotoner Stack mit 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)Ansatz 1: Vorab berechnete Maximalwert-Arrays
Die direkte Lösung mit O(n) Zeit und O(n) Speicher berechnet zunächst zwei Arrays: max_left[i] = die maximale Höhe von Index 0 bis i und max_right[i] = die maximale Höhe von Index i bis n-1. Das Wasser an Position i ist max(0, min(max_left[i], max_right[i]) - height[i]).
Für den Aufbau von max_left ist ein einziger Durchlauf von links nach rechts erforderlich; für max_right ein Durchlauf von rechts nach links. In einem letzten Durchlauf wird das Wasser summiert. Dieser Ansatz ist übersichtlich und leicht zu erklären, benötigt aber O(n) zusätzlichen Speicher.
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])) # 9Ansatz 2: Zwei Zeiger (O(1) Speicher)
Der Zwei-Zeiger-Ansatz erreicht O(n) Zeit und O(1) Speicher. Verwenden Sie einen linken und einen rechten Zeiger, die an den beiden Enden beginnen. Verwalten Sie max_left und max_right als laufende Maxima, die bisher von jeder Seite aus gesehen wurden.
Verarbeiten Sie in jedem Schritt die Seite mit dem kleineren laufenden Maximum – denn diese Seite ist der begrenzende Faktor. Wenn max_left < max_right gilt, beträgt das Wasser am linken Zeiger max_left - height[left] (die rechte Seite ist hoch genug). Bewegen Sie den linken Zeiger nach innen. Andernfalls verarbeiten Sie symmetrisch den rechten Zeiger. Vorab berechnete Arrays sind nicht erforderlich.
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])) # 3Warum zwei Zeiger funktionieren: Die Invariante
Die entscheidende Erkenntnis: Wenn wir den linken Zeiger verarbeiten, weil height[left] < height[right] gilt, wissen wir, dass max_right >= height[right] > height[left]. Daher ist die effektive Wasserbegrenzung rechts mindestens height[right] und damit bereits größer als max_left. Also gilt min(max_left, effective_max_right) = max_left, und die Wasserformel vereinfacht sich zu max_left - height[left].
Wir müssen den genauen Wert von max_right nicht kennen – es reicht zu wissen, dass er mindestens height[right] > height[left] ist, um max_left als Wasserstand zu verwenden. Diese elegante Invariante macht O(1) Speicher möglich.
# 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)Ansatz 3: Monotoner Stack (horizontale Schichten)
Der Ansatz mit einem monotonen Stack berechnet Wasser in horizontalen Schichten zwischen benachbarten Balken. Halten Sie einen monoton fallenden Stack von Indizes aufrecht. Wenn Balken i höher ist als das oberste Element j des Stacks, entsteht eine Senke: Der Boden ist height[j], die linke Begrenzung ist nach dem Entfernen von j height[stack[-1]] und die rechte Begrenzung ist height[i]. Wasser füllt die Senke bis zu min(left_wall, right_wall) - floor, mit der Breite i - stack[-1] - 1.
Jede „Senke“ wird berechnet, sobald ein höherer Balken gefunden wird. So wird das Wasser in begrenzten rechteckigen Abschnitten verarbeitet. Das ist nützlich, wenn Sie zusätzlich verfolgen müssen, welche Balken zum Wasserstand beitragen.
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])) # 9Nachverfolgen des monotonen Stacks
Verfolgen wir [0,1,0,2,1,0,1,3,...] mit dem Stack-Ansatz. Wenn wir bei i=3 auf Balken 3 (h=2) treffen: Das oberste Stack-Element ist i=2 (h=0), also entfernen wir es. Die linke Begrenzung ist i=1 (h=1), die rechte Begrenzung ist h=2. Wasserhöhe = min(1,2)-0=1, Breite=3-1-1=1, Fläche=1. Fahren Sie fort: Das oberste Stack-Element i=1 (h=1) ist nicht kleiner als 2, also beenden Sie die Verarbeitung. Legen Sie 3 auf den Stack.
Der Stack-Ansatz ist komplexer zu implementieren als der Zwei-Zeiger-Ansatz, zeigt aber, welche konkreten Balken jede einzelne Wasserzelle bilden. Diese Erkenntnis ist bei weiterführenden Fragen zur Rekonstruktion der Wasserverteilung oder zum Zählen unterschiedlicher Senken nützlich.
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)Vergleich aller drei Ansätze
Zusammenfassung der drei Ansätze zum Auffangen von Regenwasser:
- Präfix-Arrays: Laufzeit O(n), Speicherbedarf O(n). Am einfachsten zu verstehen und zu überprüfen. Am besten für Interviews geeignet, bei denen Verständlichkeit wichtiger ist als Speichereffizienz.
- Zwei Zeiger: Laufzeit O(n), Speicherbedarf O(1). Sowohl zeitlich als auch beim Speicherbedarf optimal. Am besten für Rückfragen wie „Können Sie das mit O(1) Speicher lösen?“ geeignet.
- Monotoner Stack: Laufzeit O(n), Speicherbedarf O(n). Verarbeitet Wasser in horizontalen Schichten. Am besten geeignet, wenn Sie wissen müssen, welche Balken beitragen, oder wenn dieses Problem als Teilproblem in einem größeren Stack-basierten Algorithmus auftritt.
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}')Container mit dem meisten Wasser
Container mit dem meisten Wasser (LeetCode 11) wird häufig mit dem Auffangen von Regenwasser verwechselt. Hier wählen Sie genau zwei Balken aus, und das Wasser wird nur durch diese beiden Balken begrenzt (innere Balken spielen keine Rolle). Maximieren Sie die Fläche min(height[l], height[r]) × (r - l).
Zwei Zeiger lösen das Problem mit einem Greedy-Ansatz: Beginnen Sie an beiden Enden (maximale Breite). Bewegen Sie den Zeiger am kürzeren Balken nach innen – den höheren Zeiger zu bewegen, kann die Fläche nur verringern. Die Laufzeit beträgt O(n), der Speicherbedarf O(1). Damit ist dieser Ansatz einfacher als der Zwei-Zeiger-Ansatz zum Auffangen von Regenwasser, da kein laufendes Maximum benötigt wird.
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 mapFortgeschritten: Regenwasser auffangen II (3D)
Regenwasser auffangen II (LeetCode 407) erweitert das Problem auf eine zweidimensionale Höhenmatrix. Wasser kann in alle vier Richtungen abfließen und muss über den Rand entweichen. Die Lösung verwendet einen Min-Heap: Initialisieren Sie den Heap mit allen Randzellen und führen Sie anschließend eine BFS-artige Ausbreitung durch. Verarbeiten Sie die Zelle mit der kleinsten Höhe – jeder niedrigere Nachbar muss Wasser mindestens auf Höhe der aktuellen Zelle aufnehmen.
Dies ist ein grundlegend anderer Algorithmus als im 1D-Fall und prüft sowohl Heap-Operationen als auch die BFS-Durchquerung. Der 1D-Zwei-Zeiger-Trick lässt sich nicht auf 2D verallgemeinern; der Heap-Ansatz schon.
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)) # 4Wann welche Methode in Interviews verwendet wird
Entscheidungsleitfaden für das Interview zum Auffangen von Regenwasser:
- Beginnen Sie mit: Präfix-Arrays – leicht zu erklären, visuell intuitiv und eindeutig korrekt
- Rückfrage „O(1) Speicher?“: Zwei Zeiger – erklären Sie die Invariante, dass die kleinere Seite den Engpass bildet
- Wenn der Interviewer nach einem anderen Ansatz fragt: Monotoner Stack – erklären Sie die Berechnung in horizontalen Schichten
Definieren Sie immer zuerst klar, was den Wasserstand an jeder Position bestimmt (das Minimum des höchsten Balkens auf jeder Seite), bevor Sie zu Code übergehen. Das zeigt, dass Sie das Problem verstanden haben, und erleichtert die Erklärung der Lösung.
# 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()Sonderfälle und häufige Fehler
Häufige Fehler beim Auffangen von Regenwasser:
- min vergessen: Der Wasserstand ist
min(max_left, max_right), nicht nur einer dieser beiden Werte. Ein Balken benötigt auf beiden Seiten hohe Begrenzungen. - Negatives Wasser: Verwenden Sie
max(0, ...), um negative Werte auf 0 zu begrenzen, wenn die Höhe einer Position den Wasserstand überschreitet. - Randpositionen: Der am weitesten links und der am weitesten rechts stehende Balken können niemals Wasser aufnehmen, da auf einer Seite eine Begrenzung fehlt. Der Präfix-Array-Ansatz behandelt dies automatisch, da
max_left[0] = height[0]den Wasserstand am Index 0 immer auf 0 setzt. - Leere oder sehr kleine Arrays: Geben Sie für Arrays mit weniger als 3 Elementen 0 zurück.
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 waterKurzer Test
Testen Sie Ihr Verständnis der Konzepte aus der Lektion Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Regenwasser wird aufgefangen, indem an jeder Position das Minimum der höchsten linken und rechten Begrenzung bestimmt wird, der Zwei-Zeiger-Ansatz mit O(1) zusätzlichem Speicher funktioniert, weil das laufende Maximum auf der kleineren Seite immer die maßgebliche Begrenzung ist und der Ansatz mit monotonem Stack Wasser in horizontalen Schichten berechnet und sich eignet, wenn er mit anderer Stack-Logik kombiniert wird. Als Nächstes wechseln wir zu Konzepten des Systemdesigns und beginnen mit dem RADIO-Framework für strukturierte Interviewantworten.
Lerne Python mit einem KI-Tutor — kostenlos
Schreibe und führe echten Code in deinem Browser aus, bekomme sofortige Hilfe von einem 24/7 KI-Tutor und setze dein Lernen im Web oder in der App fort.
- Kurse
- 30
- Lektionen
- 120
Häufig gestellte Fragen
Ist die Lektion „Trapping Rain Water: Stack und Zwei-Zeiger“ kostenlos?
Ja — der vollständige Text von „Trapping Rain Water: Stack und Zwei-Zeiger“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Trapping Rain Water: Stack und Zwei-Zeiger“?
Lösen Sie trapping-rain-water sowohl mit dem monotonen Stack, der horizontale Schichten berechnet, als auch mit dem Zwei-Zeiger-Ansatz, der vertikale Säulen berechnet. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Trapping Rain Water: Stack und Zwei-Zeiger“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Monotoner Stack: aufsteigend vs. absteigend
- Größtes Rechteck im Histogramm
- Sliding-Window-Maximum mit monotoner Deque
- Trapping Rain Water: Stack und Zwei-Zeiger