Container With Most Water

Q: Wie hoch ist die Zeitkomplexität von „Container With Most Water“?

Die Lösung mit zwei Zeigern benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz. Bei jedem Schritt wird ein Zeiger um eine Position nach innen bewegt, daher gibt es höchstens n-1 Schritte. Das Überprüfen jedes Paars benötigt O(n²), und das Sortieren der Linien nach ihrer Höhe benötigt O(n log n).

Q: Warum den Zeiger zur kürzeren Linie bewegen?

Die Wassermenge wird durch die kürzere Linie begrenzt. Jeder andere Behälter, der diese Linie enthält, hat einen näher gelegenen Partner und ist daher schmaler und nicht höher als die kürzere Linie. Keiner von ihnen kann den von dir gemessenen Behälter übertreffen, daher kann die kürzere Linie verworfen werden, ohne dass die Antwort verloren geht.

Q: Ist „Container With Most Water“ ein Greedy-Problem?

Ja. Bei jedem Schritt wird eine lokale Entscheidung getroffen, die nie rückgängig gemacht wird: Die kürzere Linie wird verworfen. Diese Entscheidung ist sicher, weil jeder Behälter, den der Schritt ausschließt, nicht besser ist als ein bereits gemessener. Deshalb wird das Problem sowohl den Greedy-Algorithmen als auch der Zwei-Zeiger-Technik zugeordnet.

Q: Worin unterscheidet sich „Container With Most Water“ von „Trapping Rain Water“?

Hier zählen nur die beiden ausgewählten Linien; die Linien dazwischen werden ignoriert, sodass die Antwort ein einzelnes Rechteck ist. Bei „Trapping Rain Water“ ist jeder Balken massiv, und Wasser sammelt sich über jedem Balken bis zur Höhe des niedrigeren der höchsten Balken auf seinen beiden Seiten. Die Antwort ist daher eine Summe über alle Positionen. Für beide Probleme gibt es O(n)-Lösungen mit zwei Zeigern, aber die Regeln für die Zeiger und die aufsummierten Werte unterscheiden sich.

MittelZwei Zeiger Greedy

+10

Du erhältst eine Liste height aus nicht negativen ganzen Zahlen. Die Linie i ist eine senkrechte Wand mit der Höhe height[i], die an Position i steht. Je zwei Linien bilden zusammen mit dem Boden einen Behälter, der so viel Wasser fasst wie die Höhe der kürzeren Linie multipliziert mit dem Abstand zwischen den beiden Linien. Die anderen Linien stehen nicht im Weg. Gib die größte Wassermenge zurück, die ein einzelnes Linienpaar fassen kann.

Funktion

maxArea(height: integer-array) → integer

heightinteger-array: die Höhen der Zeilen an den Positionen 0, 1, 2 usw.
Gibt zurückinteger: die größte Wassermenge, die zwei Zeilen fassen können

Einschränkungen

2 ≤ height.length ≤ 10⁴
0 ≤ height[i] ≤ 10⁴
Die Antwort ist höchstens 10⁸, daher passt sie in eine 32-Bit-Ganzzahl.

Beispiele

Eingabe: height = [3, 7, 2, 5, 4, 7, 3, 6]
Ausgabe: 36
Erklärung: Die Linien an den Positionen 1 und 7 haben die Höhen 7 und 6 und liegen 6 auseinander, also fassen sie 6 × 6 = 36. Die beiden höchsten Linien, die 7er an den Positionen 1 und 5, fassen nur 7 × 4 = 28, und das äußere Paar fasst 3 × 7 = 21.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Hier werden die Linien zwischen den beiden, die du auswählst, ignoriert. Wie viel Wasser würde sich zwischen all diesen Linien sammeln, wenn jede Linie stattdessen ein durchgehender Balken wäre? Kannst du das ebenfalls in O(n) berechnen?

Lösung

Es gibt etwa n²/2 Linienpaare. Bei 10^4 Linien bedeutet es also 5 × 10^7 Produkte, alle zu überprüfen. Der Ausweg: Die Wassermenge hängt nur von der kürzeren Linie eines Paars ab. Sobald du weißt, dass eine Linie die kürzere Seite des breitesten Behälters ist, den sie bilden kann, kann kein schmalerer Behälter mit dieser Linie mehr Wasser fassen. Zwei Zeiger machen aus dieser Beobachtung einen einzigen Durchlauf von beiden Enden aus.

Überprüfe jedes Paar

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Jeder Behälter wird durch ein Paar von Positionen i < j gebildet. Das Wasser steigt, bis es über die niedrigere Wand läuft, und der Boden zwischen den Wänden ist j - i breit. Daher fasst das Paar min(height[i], height[j]) × (j - i). Probiere jedes Paar aus, behalte das größte und du hast per Definition die Antwort.

Der Haken ist die Anzahl der Paare. n Linien ergeben n(n-1)/2 Paare: etwa 5 × 10^7 bei 10^4 Linien, und jedes Mal, wenn sich die Liste verdoppelt, sind es viermal so viele. Eine kompilierte Sprache schafft das in einem Bruchteil einer Sekunde, aber Python, Ruby oder R benötigen viele Sekunden, und die Anzahl wächst für jede Sprache zu schnell, sobald n 10^5 erreicht.

Algorithmus

Setze best auf 0.
Berechne für jedes i und jedes darauffolgende j min(height[i], height[j]) × (j - i).
Behalte den größeren Wert von best und diesem Wert bei.
Gib best zurück.

def maxArea(height):
    n = len(height)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            best = max(best, water)
    return best

Die höchsten Zeilen zuerst

Idee

Betrachte einen Behälter von der Seite seiner kürzeren Linie aus. Wenn Linie i die kürzere Seite ist, beträgt die Wassermenge height[i] mal dem Abstand, und die Partnerlinie kann eine beliebige mindestens ebenso hohe Linie sein. Der beste Behälter, bei dem i die kürzere Seite ist, bildet also mit der am weitesten entfernten Linie, die mindestens ebenso hoch ist, ein Paar.

Um diese Partner schnell zu finden, ordne die Linien von der höchsten bis zur niedrigsten. Wenn Linie i an die Reihe kommt, ist jede zuvor eingeordnete Linie mindestens ebenso hoch, und die am weitesten entfernte davon ist entweder der ganz links oder der ganz rechts eingeordnete Index. Verfolge diese beiden Indizes, lo und hi, und Linie i fasst höchstens height[i] × max(i - lo, hi - i). Die Antwort ist der größte dieser Werte, denn der beste Behälter wird gezählt, wenn seine kürzere Linie an die Reihe kommt.

Im ersten Beispiel kommen die beiden 7er an den Positionen 1 und 5 zuerst und fassen 28. Als Nächstes kommt die 6 an Position 7, mit lo = 1 und hi = 5, und fasst 6 × 6 = 36. Keine kürzere Linie übertrifft diesen Wert. Linien gleicher Höhe können in beliebiger Reihenfolge kommen: Diejenige von zwei gleich hohen Linien, die als Zweite an die Reihe kommt, sieht die erste als Partner.

Das Sortieren kostet O(n log n) und der Durchlauf O(n), was schnell genug ist. Es benötigt weiterhin O(n) Speicher für die Reihenfolge, und der nächste Ansatz kommt ohne Sortierung und Speicher aus.

Algorithmus

Sortiere die Indizes nach Höhe, beginnend mit dem höchsten.
Setze lo und hi auf den ersten Index dieser Reihenfolge und best auf 0.
Berechne für jeden nächsten Index i height[i] multipliziert mit dem größeren der Werte i - lo und hi - i, und behalte den besten Wert bei.
Aktualisiere lo und hi, sodass sie auch i einschließen.
Gib best zurück.

def maxArea(height):
    # Indices from the tallest line to the shortest.
    order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
    lo = hi = order[0]  # leftmost and rightmost index among the lines placed so far
    best = 0
    for i in order[1:]:
        # Every placed line is at least as tall as line i, so line i is the
        # shorter side, and its best partner is the placed line farthest away.
        best = max(best, height[i] * max(i - lo, hi - i))
        lo = min(lo, i)
        hi = max(hi, i)
    return best

Zwei Zeiger von beiden Enden

Idee

Beginne mit dem breitesten Behälter, left = 0 und right = n-1, und miss ihn. Nun kann eine der beiden Linien wegfallen, und die Wahl ist vorgegeben: Entferne die kürzere. Angenommen, height[left] ≤ height[right]. Jeder andere Behälter, der die Linie left verwendet, kombiniert sie mit einer Linie, die näher als right liegt. Er ist also schmaler, und seine Höhe ist weiterhin höchstens height[left]. Keiner dieser Behälter enthält mehr Wasser als der gemessene, also ist die Linie left erledigt und left rückt einen Schritt nach rechts. Würde man stattdessen die höhere Linie verschieben, bliebe dieselbe Begrenzung für die Höhe bestehen, während die Breite abnimmt – das kann also nur schlechter sein. Sind die beiden Höhen gleich, sind beide Linien erledigt, und es ist egal, welche man verschiebt.

Bei jedem Schritt wird eine Linie endgültig aussortiert, also treffen sich die Zeiger nach n-1 Schritten. Das beste Linienpaar wird nie übersprungen: Wenn zum ersten Mal eine seiner beiden Linien aussortiert wird, enthält der in diesem Moment gemessene Behälter mindestens genauso viel Wasser.

Bei [3, 7, 2, 5, 4, 7, 3, 6] fassen die Positionen 0 und 7 3 × 7 = 21. Die 3 ist kürzer, also rückt left auf 1. Die Positionen 1 und 7 fassen 6 × 6 = 36, und nun ist die 6 kürzer, also rückt right auf 6. Die folgenden Behälter fassen 15, 28, 12, 10 und 2, daher bleibt das Ergebnis 36.

Algorithmus

Setze left = 0, right = n-1 und best = 0.
Solange left < right gilt, berechne min(height[left], height[right]) × (right - left) und behalte den besten Wert.
Wenn height[left] < height[right] gilt, bewege left einen Schritt nach rechts. Andernfalls bewege right einen Schritt nach links.
Wenn sich die Zeiger treffen, gib best zurück.

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        best = max(best, water)
        # The shorter line cannot do better with any line closer in, so drop it.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

Stolperfallen und Grenzfälle

Die Schleife mit zwei Zeigern ist kurz, die Fehler stecken also im Detail.

Die höhere Linie verschieben. Im ersten Beispiel ergibt das 21 statt 36: Die 6 an Position 7 ist die höhere Linie des ersten Paares und wird daher verschoben, bevor sie jemals auf die 7 an Position 1 trifft.
Die höhere Linie oder den Durchschnitt der beiden als Höhe verwenden. Wasser läuft über die kürzere Wand, daher ist die Höhe das Minimum.
Ein Off-by-one-Fehler bei der Breite. Linien an den Positionen i und j sind j - i voneinander entfernt, nicht j - i + 1, daher fassen zwei Nachbarn ihre kürzere Höhe mal 1.
Annehmen, dass die Antwort die höchste Linie oder das äußere Paar verwendet. Im ersten Beispiel fassen die beiden 7er 28 und das äußere Paar 21, während die Antwort 36 ist.
Überlauf bei größeren Grenzen. Hier bleibt das Wasser unter 10^8, aber bei Höhen und Längen nahe 10^5 überschreitet das Produkt 2^31 und erfordert eine 64-Bit-Ganzzahl.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von „Container With Most Water“?

Die Lösung mit zwei Zeigern benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz. Bei jedem Schritt wird ein Zeiger um eine Position nach innen bewegt, daher gibt es höchstens n-1 Schritte. Das Überprüfen jedes Paars benötigt O(n²), und das Sortieren der Linien nach ihrer Höhe benötigt O(n log n).

Warum den Zeiger zur kürzeren Linie bewegen?

Die Wassermenge wird durch die kürzere Linie begrenzt. Jeder andere Behälter, der diese Linie enthält, hat einen näher gelegenen Partner und ist daher schmaler und nicht höher als die kürzere Linie. Keiner von ihnen kann den von dir gemessenen Behälter übertreffen, daher kann die kürzere Linie verworfen werden, ohne dass die Antwort verloren geht.

Ist „Container With Most Water“ ein Greedy-Problem?

Ja. Bei jedem Schritt wird eine lokale Entscheidung getroffen, die nie rückgängig gemacht wird: Die kürzere Linie wird verworfen. Diese Entscheidung ist sicher, weil jeder Behälter, den der Schritt ausschließt, nicht besser ist als ein bereits gemessener. Deshalb wird das Problem sowohl den Greedy-Algorithmen als auch der Zwei-Zeiger-Technik zugeordnet.

Worin unterscheidet sich „Container With Most Water“ von „Trapping Rain Water“?

Hier zählen nur die beiden ausgewählten Linien; die Linien dazwischen werden ignoriert, sodass die Antwort ein einzelnes Rechteck ist. Bei „Trapping Rain Water“ ist jeder Balken massiv, und Wasser sammelt sich über jedem Balken bis zur Höhe des niedrigeren der höchsten Balken auf seinen beiden Seiten. Die Antwort ist daher eine Summe über alle Positionen. Für beide Probleme gibt es O(n)-Lösungen mit zwei Zeigern, aber die Regeln für die Zeiger und die aufsummierten Werte unterscheiden sich.

Python

def maxArea(height):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

height = [3, 7, 2, 5, 4, 7, 3, 6]

Erwartet

Container With Most Water

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Überprüfe jedes Paar

Die höchsten Zeilen zuerst

Zwei Zeiger von beiden Enden

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben