Trapping Rain Water
Eine Reihe von Balken steht nebeneinander, jeder ist eine Einheit breit: height[i] ist die Höhe des Balkens i. Regen fällt auf die Reihe und sammelt sich in den Vertiefungen zwischen den Balken. Wasser bleibt nur dann über einem Balken stehen, wenn links und rechts davon irgendwo ein höherer Balken steht; hinter dem ersten und dem letzten Balken läuft es ab.
Gib die Gesamtzahl der Einheitsquadrate Wasser zurück, die die Reihe aufnehmen kann.
Funktion
- heightinteger-array
- die Höhe jedes Balkens, von links nach rechts
- Gibt zurückinteger
- die Gesamtmenge des eingeschlossenen Wassers
Einschränkungen
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- Jeder Balken ist eine Einheit breit, und das Wasser bleibt nicht über den ersten oder den letzten Balken hinaus stehen.
Beispiele
- Eingabe
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- Ausgabe
- 7
- Erklärung
- Zwischen der 3 und der 5 steigt das Wasser bis auf Höhe 3: Es hält 2 Einheiten über dem Balken der 1, 3 über der 0 und 1 über der 2. Die 1 nahe dem Ende liegt zwischen einer 5 und einer 2, daher ist ihre Höhe 2 und sie hält 1 Einheit. 2 + 3 + 1 + 1 = 7.
- Eingabe
- height = [4, 1, 3, 0, 5]
- Ausgabe
- 8
- Erklärung
- Die niedrigere Wand ist die 4 links, daher füllt sich die gesamte Senke bis zur Höhe 4: 3 Einheiten über der 1, 1 über der 3 und 4 über der 0, also insgesamt 8. Die 5 rechts erhöht den Wasserstand nicht, weil das Wasser zuerst über die 4 laufen würde.
- Eingabe
- height = [1, 2, 4, 2, 1]
- Ausgabe
- 0
- Erklärung
- Die Balken steigen auf 4 und fallen wieder ab. Jeder Balken hat eine Seite, hinter der nichts Höheres liegt, sodass das Wasser abfließt und das Ergebnis 0 ist.
+17 versteckte Tests beim Einreichen
Weiterführende Frage
Angenommen, die Balken bilden ein zweidimensionales Raster aus Höhen und das Wasser kann in alle vier Richtungen abfließen. Wie würdest du dann das eingeschlossene Wasser zählen?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Vergiss die ganze Reihe und betrachte einen Balken. Wie hoch kann das Wasser über Balken
istehen, und welche Balken bestimmen diese Höhe?Der Wasserstand über Balken
ientspricht dem kleineren von zwei Werten: dem höchsten Balken vom Anfang bisiund dem höchsten Balken vonibis zum Ende. Balkenienthält die Differenz zwischen diesem Wasserstand und seiner eigenen Höhe. Beide laufenden Maxima lassen sich in einem Durchlauf von jedem Ende aus ermitteln.Du benötigst nur den kleineren der beiden Maximalwerte. Setze je einen Zeiger an jedes Ende und merke dir für jeden Zeiger den höchsten Balken, den er bisher passiert hat. Der Zeiger, der auf dem niedrigeren Balken steht, hat sein Niveau durch sein eigenes bisheriges Maximum bestimmt: Addiere dieses Wasser und bewege diesen Zeiger nach innen. Höre auf, wenn sich die Zeiger treffen.
Lösung
Die Wassermenge über jedem Balken hängt von Balken ab, die auf beiden Seiten weit entfernt sein können. Daher führt ein lokaler Blick auf die Nachbarbalken zum falschen Ergebnis. Die Lösung ist eine Formel: Die Wasserhöhe über einem Balken ist das Minimum aus der höchsten Höhe links davon und der höchsten Höhe rechts davon. Diese beiden Maxima für jeden Balken durch Scannen zu ermitteln, ist langsam; sie in zwei Arrays zu speichern, macht den Algorithmus linear, und zwei Zeiger, von denen immer der auf der niedrigeren Seite weitergeschoben wird, kommen ganz ohne Arrays aus.
Scanne beide Seiten jedes Takts.
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Zähle das Wasser Spalte für Spalte. Das Wasser über Balken i steigt, bis es über die niedrigere seiner beiden Begrenzungen laufen würde. Die linke Begrenzung ist der höchste Balken an einer beliebigen Stelle vom Index 0 bis i; die rechte Begrenzung ist der höchste Balken von i bis zum Ende. Der Wasserstand ist also min(leftMax, rightMax), und die Wassermenge über Balken i entspricht diesem Wasserstand minus height[i].
Nimm [0, 3, 1, 0, 2, 5, 1, 2] und den Balken der Höhe 0 am Index 3. Der höchste Balken links davon ist 3, rechts davon 5. Der Wasserstand beträgt 3, dort stehen also 3 Einheiten Wasser. Beim Balken der Höhe 1 am Index 6 sind die Begrenzungen 5 und 2: Der Wasserstand beträgt 2, und der Balken hält 1 Einheit Wasser.
Beide Durchläufe schließen Balken i selbst ein. So wird verhindert, dass das Ergebnis negativ wird: Wenn Balken i höher ist als alles auf einer Seite, entspricht das Maximum auf dieser Seite seiner eigenen Höhe, der Wasserstand entspricht seiner Höhe und der Balken hält 0 Einheiten Wasser. Deshalb halten auch der erste und der letzte Balken immer 0 Einheiten Wasser.
Das Problem sind die Kosten. Für jeden Balken wird die ganze Reihe durchlaufen, zur Hälfte nach links und zur Hälfte nach rechts, also insgesamt n × n Lesezugriffe: 4 × 10^8 für 2 × 10^4 Balken. Außerdem wiederholen sich die Durchläufe: Der höchste Balken links vom Index 5 ist der höchste Balken links vom Index 4 plus ein weiterer Vergleich, aber beim Brute-Force-Ansatz wird er von null an erneut berechnet.
Algorithmus
- Setze
waterauf 0. - Durchlaufe für jeden Index
idie Indizes von 0 bisi, umleftMaxzu ermitteln. - Durchlaufe die Indizes von
ibis zum letzten Index, umrightMaxzu ermitteln. - Addiere
min(leftMax, rightMax) - height[i]zuwater. - Gib
waterzurück.
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 waterBerechne den höchsten Balken auf jeder Seite im Voraus
Idee
Die Formel bleibt bestehen; nur die Art, wie du die beiden Wände bestimmst, ändert sich. Der höchste Balken von 0 bis i ist der größere Wert aus dem höchsten Balken von 0 bis i-1 und height[i]. Ein Durchlauf von links nach rechts füllt also ein Array leftMax, wobei jeder Eintrag aus dem vorherigen gebildet wird. Ein Durchlauf von rechts nach links füllt rightMax auf dieselbe Weise. Ein dritter Durchlauf addiert für jeden Balken min(leftMax[i], rightMax[i]) - height[i].
Für [0, 3, 1, 0, 2, 5, 1, 2]: leftMax = [0, 3, 3, 3, 3, 5, 5, 5] und rightMax = [5, 5, 5, 5, 5, 5, 2, 2]. Die jeweils kleineren Werte ergeben die Höhen [0, 3, 3, 3, 3, 5, 2, 2]. Ziehst du die Balkenhöhen ab, erhältst du [0, 0, 2, 3, 1, 0, 1, 0], deren Summe 7 ist.
Jeder Durchlauf berücksichtigt jeden Balken genau einmal, also beträgt die Laufzeit O(n): etwa 6 × 10^4 Schritte für 2 × 10^4 Balken statt 4 × 10^8. Der Preis dafür sind zwei zusätzliche Arrays mit jeweils n Zahlen. In einem Vorstellungsgespräch solltest du zuerst diese Variante wählen: Sie ist schwer falsch umzusetzen, und der nächste Ansatz dient dazu, die Arrays wegzulassen, nicht einer anderen Idee.
Algorithmus
- Fülle
leftMaxvon links nach rechts:leftMax[0] = height[0], dannleftMax[i] = max(leftMax[i-1], height[i]). - Fülle
rightMaxvon rechts nach links:rightMax[n-1] = height[n-1], dannrightMax[i] = max(rightMax[i+1], height[i]). - Addiere für jeden Index
min(leftMax[i], rightMax[i]) - height[i]zur Gesamtsumme. - Gib die Gesamtsumme zurück.
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 waterZwei Zeiger, die sich auf der unteren Seite bewegen
Idee
Die Formel benötigt nur die niedrigere der beiden Wände. Wenn du beweisen kannst, dass die linke Wand an einem bestimmten Index die niedrigere ist, brauchst du die rechte Wand dieses Indexes überhaupt nicht. Zwei Zeiger liefern diesen Beweis. Setze left auf Index 0 und right auf den letzten Index und behalte leftMax und rightMax im Blick, also die höchste Säule, an der jeder Zeiger bisher vorbeigekommen ist, einschließlich der Säule, auf der er gerade steht.
Die Invariante: Jede Säule, an der die Zeiger bereits vorbeigekommen sind, ist nicht höher als die höhere der beiden Säulen, auf denen sie jetzt stehen. Das gilt, weil du immer den Zeiger auf der niedrigeren Säule bewegst. Ein Zeiger geht also nur an einer Säule vorbei, die nicht höher ist als die Säule unter dem anderen Zeiger.
Angenommen, height[left] < height[right]. Nach der Invariante ist leftMax höchstens height[right], und height[right] ist selbst eine Säule rechts von left. Die tatsächliche rechte Wand von left ist also mindestens so hoch wie leftMax, und der Wasserstand bei left entspricht genau leftMax, unabhängig davon, was zwischen den Zeigern liegt. Addiere leftMax - height[left] und bewege left einen Schritt nach rechts. Wenn height[right] die niedrigere oder gleich hohe Säule ist, gehst du auf der rechten Seite spiegelbildlich vor. Aktualisiere das laufende Maximum, bevor du das Wasser addierst, damit die Säule unter dem Zeiger als eigene Wand zählt und die Wassermenge niemals negativ ist.
Gehe [0, 3, 1, 0, 2, 5, 1, 2] Schritt für Schritt durch. Die Zeiger starten bei 0 und 2: links ist niedriger, dort sammelt sich 0. Als Nächstes 3 gegen 2: rechts ist niedriger, rightMax wird zu 2, dort sammelt sich 0. Dann 3 gegen 1: rechts ist wieder niedriger, bei der 1 sammeln sich 2-1 = 1. Dann 3 gegen 5: jetzt ist links niedriger, leftMax ist 3. Bei der 3 sammeln sich 0, bei der 1 sammeln sich 2, bei der 0 sammeln sich 3 und bei der 2 sammeln sich 1. Die Zeiger treffen sich bei der 5. Insgesamt sind es 1 + 2 + 3 + 1 = 7, mit einem Durchlauf und vier Variablen.
Algorithmus
- Setze
left = 0,right = n-1undleftMax,rightMaxsowiewaterauf 0. - Solange
left < right, vergleicheheight[left]mitheight[right]. - Wenn die linke Säule niedriger ist, erhöhe
leftMaxbei Bedarf aufheight[left], addiere leftMax - height[left] und bewegeleftnach rechts. - Andernfalls erhöhe
rightMaxbei Bedarf aufheight[right], addiere rightMax - height[right] und bewegerightnach links. - Gib
waterzurück, wenn sich die Zeiger treffen; die Säule, auf der sie sich treffen, ist die höchste und hält kein Wasser.
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
Stolperfallen und Grenzfälle
Die Formel ist kurz, und die meisten falschen Antworten entstehen durch die Reihenfolge zweier Zeilen oder dadurch, welche Seite du verschiebst.
- Das Wasser hinzufügen, bevor du das laufende Maximum aktualisierst. Wenn
height[left]höher alsleftMaxist, istleftMax - height[left]negativ und die Summe wird kleiner. Aktualisiere zuerst das Maximum und addiere dann. - Den Zeiger auf der höheren Säule verschieben. Das Niveau ist nur auf der niedrigeren Seite bekannt; die höhere Seite zu verschieben, verwendet eine Begrenzung, die du nicht bewiesen hast. Bei
[4, 1, 3, 0, 5]gibt diese Variante 4 statt 8 zurück. - Nur die direkten Nachbarn betrachten. Die Begrenzungen einer Säule können weit entfernt sein: In
[3, 0, 2, 0, 1, 0, 4]hält die Säule mit Höhe 1 Wasser bis zum Niveau 3, das durch Säulen bestimmt wird, die vier beziehungsweise zwei Schritte entfernt sind. Die Antwort ist dort 12. - Die Enden des Arrays als Begrenzungen behandeln. Wasser, das über die erste oder letzte Säule hinausfließt, läuft ab. Daher hält eine einzelne Säule, zwei Säulen oder eine Reihe, die nur ansteigt oder nur abfällt, 0 Wasser.
- Die Säule
ibei der Brute-Force-Methode von ihren eigenen Durchläufen ausschließen. Dann ergibt eine Säule, die höher als beide Seiten ist, eine negative Wassermenge. Beziehe sie mit ein oder begrenze das Ergebnis auf mindestens 0. - Überlauf in einer Variante, die multipliziert. Hier erreicht die Antwort etwa 2 × 10^9 (zwei Säulen mit Höhe 10^5 umgeben 19,998 leere Zellen), was noch in eine vorzeichenbehaftete 32-Bit-Ganzzahl passt; verwende in deinen eigenen Varianten 64-Bit-Summen.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität von Trapping Rain Water?
Die Lösung mit zwei Zeigern benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz: Bei jedem Schritt wird ein Zeiger nach innen bewegt, also gibt es n-1 Schritte. Die Variante mit leftMax- und rightMax-Arrays benötigt ebenfalls O(n) Zeit, aber O(n) Speicherplatz. Von jedem Balken aus beide Seiten zu durchlaufen, benötigt O(n²) Zeit, etwa 4 × 10^8 Lesezugriffe bei 2 × 10^4 Balken.
Warum kann die Zwei-Zeiger-Lösung die kürzere Seite verschieben?
Jeder bereits passierte Balken ist nicht höher als der höhere der beiden aktuellen Balken, denn nur der niedrigere Zeiger bewegt sich. Wenn also der linke Balken niedriger ist, ist sein bisheriges Maximum höchstens so hoch wie der rechte Balken, und der rechte Balken bildet rechts davon eine tatsächliche Begrenzung. Der Wasserstand am linken Zeiger entspricht seinem bisherigen Maximum, unabhängig davon, was zwischen den Zeigern liegt. Daher kannst du diesen Balken endgültig bestimmen und weitermachen.
Kann man das Problem „Trapping Rain Water“ mit einem Stack lösen?
Ja. Behalte einen Stapel von Indizes, deren Höhen von unten nach oben abnehmen. Wenn ein Balken eintrifft, der höher als der oberste ist, entferne den obersten: Er ist der Boden eines Beckens, dessen Wände der neue oberste Stapelwert und der aktuelle Balken sind. Addiere (min(two walls) - floor) × (distance between the walls - 1) und entferne weiter Elemente, solange der aktuelle Balken höher ist. Der Stapel füllt das Wasser in horizontalen Schichten statt in Säulen auf, in O(n) Zeit und mit O(n) Speicherplatz.
Wie unterscheidet sich das Auffangen von Regenwasser vom Behälter mit dem meisten Wasser?
Bei „Container With Most Water“ wählst du zwei Linien aus, und die Linien dazwischen nehmen keinen Platz ein, sodass die Antwort ein einziges Rechteck ist, das größtmögliche. Hier ist jeder Balken gefüllt, das Wasser steht auf jedem Balken, und die Antwort ist die Summe über alle Balken. Bei beiden werden zwei Zeiger verwendet, die sich auf die niedrigere Seite zubewegen, und zwar aus demselben Grund: Das Ergebnis für die niedrigere Seite steht bereits fest.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def trap(height):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
height = [0, 3, 1, 0, 2, 5, 1, 2]
Erwartet
7