Trapping Rain Water
Eine Reihe von Balken steht nebeneinander, jeder ist eine Einheit breit: height[i] ist die Höhe des Balkens i. Regenwasser sammelt sich in den Vertiefungen zwischen den Balken. Wasser bleibt nur dann über einem Balken stehen, wenn links und rechts davon jeweils irgendwo ein höherer Balken steht; am ersten und am letzten Balken läuft es ab. Gib die Gesamtmenge an Wassereinheiten zurück, die die Reihe aufnehmen kann.
Funktion
- heightinteger-array
- die Höhe jedes Balkens, von links nach rechts
- Gibt zurückinteger
- die Gesamtmenge der eingeschlossenen Wassereinheiten
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 liegt die Ebene 3: 2 Einheiten über der 1, 3 über der 0, 1 über der 2. Die spätere 1 liegt zwischen der 5 und einer 2, also hat sie den Wert 1. Das ergibt 7.
- Eingabe
- height = [4, 1, 3, 0, 5]
- Ausgabe
- 8
- Erklärung
- Die niedrigere Wand ist die 4, also füllt sich die Senke bis zum Niveau 4: 3 Einheiten über der 1, 1 über der 3, 4 über der 0, das ergibt 8. Das Wasser läuft über die 4, bevor die 5 eine Rolle spielt.
- Eingabe
- height = [1, 2, 4, 2, 1]
- Ausgabe
- 0
- Erklärung
- Die Balken steigen bis auf 4 und fallen dann wieder. Jeder Balken hat eine Seite, hinter der nichts Höheres liegt, sodass das Wasser abfließt und das Ergebnis 0 ist.
Weiterführende Frage
Angenommen, die Balken bilden ein 2D-Raster aus Höhen und das Wasser kann in alle vier Richtungen entweichen. 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
iist der kleinere von zwei Werten: dem höchsten Balken vom Anfang bis einschließlichiund dem höchsten Balken vonibis zum Ende. Balkenifasst diesen Wasserstand abzüglich seiner eigenen Höhe. Beide laufenden Maxima lassen sich jeweils in einem Durchlauf von einem Ende aus berechnen.Du brauchst nur das kleinere der beiden Maxima. Setze an jedes Ende einen Zeiger und merke dir die höchste Säule, die jeder Zeiger bisher passiert hat. Der Zeiger, der auf der niedrigeren Säule steht, hat seinen Wasserstand durch sein bisheriges Maximum bestimmt: Addiere dieses Wasser und bewege den Zeiger nach innen. Stoppe, wenn sich die Zeiger treffen.
Lösung
Die Wassermenge über einem Balken hängt von Balken ab, die auf beiden Seiten weit entfernt sein können. Ihr Niveau entspricht dem kleineren der höchsten Balken links und rechts, und der Balken hält dieses Niveau abzüglich seiner eigenen Höhe. Die Ansätze unterscheiden sich nur darin, wie sie diese beiden Maximalwerte ermitteln.
Scanne beide Seiten ab jedem Taktstrich
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Scanne für jeden Balken i von 0 bis i nach dem höchsten Balken links und von i bis zum Ende nach dem höchsten Balken rechts. Addiere dann min(leftMax, rightMax) - height[i]. Wenn Balken i in beiden Scans enthalten ist, kann der Wert nicht negativ werden, und die Randbalken erhalten den Wert 0.
Jeder Balken durchläuft die gesamte Reihe: n = 2 × 10^4 bedeutet 4 × 10^8 Lesezugriffe, wobei die meisten den Scan des vorherigen Balkens wiederholen.
Algorithmus
- Setze
waterauf 0. - Durchsuche für jeden Index
iden Bereich von 0 bisinachleftMax. - Durchsuche den Bereich von
ibis zum letzten Index nachrightMax. - 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
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 füllt also leftMax, wobei jeder Eintrag aus dem vorherigen aufgebaut wird, und ein Durchlauf von rechts füllt rightMax. Ein dritter Durchlauf wendet die Formel an.
Für [0, 3, 1, 0, 2, 5, 1, 2] lauten die Pegel min(leftMax[i], rightMax[i]) [0, 3, 3, 3, 3, 5, 2, 2]. Zieht man die Höhen davon ab, ergibt sich [0, 0, 2, 3, 1, 0, 1, 0], deren Summe 7 beträgt. Die Laufzeit ist O(n), dafür werden jedoch zwei Arrays mit je n Zahlen benötigt.
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 niedrigeren Seite bewegen
Idee
Die Formel benötigt nur die niedrigere Wand, und mit zwei Zeigern lässt sich beweisen, welche das ist. Setze left auf 0 und right auf den letzten Index, verfolge leftMax und rightMax, also jeweils den höchsten Balken, an dem der Zeiger vorbeigekommen ist, einschließlich des Balkens unter dem Zeiger, und bewege immer den Zeiger am niedrigeren Balken. Dann ist jeder bereits passierte Balken nicht höher als der höhere der beiden aktuellen Balken, denn ein Zeiger geht nur an einem Balken vorbei, der nicht höher ist als der Balken unter dem anderen Zeiger.
Angenommen, height[left] < height[right]. Aus der Invariante folgt, dass leftMax höchstens height[right] ist, also höchstens so hoch wie ein Balken rechts von left. Die rechte Wand von left ist also mindestens so hoch wie leftMax, und sein Wasserstand entspricht genau leftMax, unabhängig davon, was zwischen den Zeigern steht. Wenn der rechte Balken niedriger oder gleich hoch ist, ergibt sich right durch das spiegelbildliche Argument.
Algorithmus
- Setze
left = 0,right = n-1undleftMax,rightMaxsowiewaterauf 0. - Solange
left < rightgilt: Fallsheight[left] < height[right]gilt, erhöheleftMaxbei Bedarf aufheight[left], addiereleftMax - height[left]und bewegeleftnach rechts. - Andernfalls verfahre auf der rechten Seite genauso und bewege
rightnach links. - Gib
waterzurück. Der Balken, an dem sich die Zeiger treffen, ist der 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
- Das Wasser hinzufügen, bevor das laufende Maximum erhöht wird. Wenn
height[left]überleftMaxliegt, ist die Menge negativ und die Gesamtsumme schrumpft. - Den Zeiger an der höheren Säule bewegen, deren Niveau nicht abgesichert ist. Bei
[4, 1, 3, 0, 5]liefert diese Version 4 statt 8 zurück. - Nur die unmittelbaren Nachbarn betrachten. Bei
[3, 0, 2, 0, 1, 0, 4]füllt sich die Säule der Höhe 1 bis zum Niveau 3, das von Säulen vier bzw. zwei Positionen entfernt bestimmt wird; die Antwort ist 12. - Die Enden des Arrays als Wände behandeln. Dort läuft das Wasser ab, daher hält eine Säule, zwei Säulen oder eine Reihe, die nur ansteigt oder nur abfällt, 0.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität des Problems „Trapping Rain Water“?
Die Lösung mit zwei Zeigern benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz, da in jedem Schritt ein Zeiger nach innen bewegt wird. Die Version mit den Arrays leftMax und rightMax benötigt ebenfalls O(n) Zeit, verwendet aber O(n) Speicherplatz. Beide Seiten von jedem Balken aus zu durchlaufen, benötigt O(n²).
Kann man das Problem „Trapping Rain Water“ mit einem Stack lösen?
Ja. Halte einen Stack von Indizes mit fallenden Höhen bereit. Wenn ein höherer Balken kommt, entferne das oberste Element: Es ist der Boden eines Beckens, dessen Wände der neue oberste Balken und der aktuelle Balken bilden. Addiere (min(two walls) - floor) × (distance between the walls - 1) und entferne weiter Elemente. So füllst du das Wasser in horizontalen Schichten, in O(n) Zeit und Speicherplatz.
Worin unterscheidet sich „Trapping Rain Water“ von „Container With Most Water“?
Bei „Container With Most Water“ nehmen die Linien keinen Platz ein, und die Antwort ist das größte Rechteck zwischen zwei Linien. Hier ist jeder Balken massiv, und die Antwort summiert das Wasser über alle Balken. In beiden Fällen wird aus demselben Grund die niedrigere Seite verschoben: Ihr Ergebnis steht bereits fest.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def trap(height):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
height = [0, 3, 1, 0, 2, 5, 1, 2]
Erwartete Ausgabe
7