Container With Most Water

Q: Wie lautet 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, da jeder Schritt einen Zeiger um eine Position nach innen bewegt. Das Überprüfen aller Paare benötigt O(n²), und das Sortieren der Linien nach Höhe benötigt O(n log n).

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

Das Wasser wird durch die kürzere Linie begrenzt. Jeder andere Behälter, der diese Linie beibehält, hat eine näher gelegene Gegenlinie, ist also schmaler und nicht höher. Keiner von ihnen kann den von dir gemessenen Behälter übertreffen, daher kann die kürzere Linie wegfallen, ohne dass das Ergebnis 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 dadurch ausgeschlossene Container nicht besser ist als ein bereits gemessener. Deshalb wird das Problem sowohl den Greedy-Algorithmen als auch der Zwei-Zeiger-Technik zugeordnet.

MittelZwei Zeiger Greedy

+10

Du erhältst eine Liste height mit nicht negativen Ganzzahlen. Die Linie i ist eine vertikale Wand der Höhe height[i] an Position i. 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 maximale Wassermenge, die zwei Zeilen fassen können

Einschränkungen

2 ≤ height.length ≤ 10⁴
0 ≤ height[i] ≤ 10⁴
Die Antwort ist höchstens 10⁸ groß und passt daher 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 mit den Höhen 7 und 6 stehen 6 Einheiten auseinander und fassen 6 × 6 = 36. Die beiden höchsten Linien, die 7er an den Positionen 1 und 5, fassen nur 7 × 4 = 28.

Weiterführende Frage

Hier werden die Linien zwischen deinen beiden ignoriert. Wenn jede Linie ein durchgehender Balken wäre, wie viel Wasser würde sich insgesamt zwischen ihnen sammeln? Kannst du das auch in O(n) berechnen?

Lösung

Alle n²/2 Paare zu prüfen, bedeutet 5 × 10^7 Produkte für 10^4 Linien. Die Wassermenge hängt nur von der kürzeren Linie eines Paares ab. Sobald eine Linie die kürzere Seite des breitesten Behälters ist, den sie noch bilden kann, kann kein schmalerer Behälter, der sie verwendet, besser sein. Zwei Zeiger machen daraus einen einzigen Durchlauf von beiden Enden aus.

Überprüfe jedes Paar

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

Idee

Ein Paar i < j ergibt min(height[i], height[j]) × (j - i): Das Wasser läuft über die kürzere Wand, und der Boden ist j - i breit. Probiere jedes Paar aus und behalte das größte.

n Linien ergeben n(n-1)/2 Paare: etwa 5 × 10^7 bei 10^4 Linien, und jedes Mal, wenn sich n verdoppelt, viermal so viele.

Algorithmus

Setze best auf 0.
Berechne für jedes i und jedes danach folgende j min(height[i], height[j]) × (j - i).
Behalte den größeren Wert von best und diesem Wert.
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

Wenn die Linie i die kürzere Seite eines Behälters ist, kann die zugehörige Linie beliebig hoch sein, solange sie mindestens genauso hoch ist. Der beste solche Behälter verbindet sie also mit der am weitesten entfernten Linie, die mindestens genauso hoch ist.

Ordne die Linien von der höchsten zur niedrigsten. Wenn Linie i an die Reihe kommt, ist jede bereits platzierte Linie mindestens genauso hoch, und die am weitesten entfernte ist der am weitesten links oder rechts platzierte Index, lo oder hi. Linie i kann also höchstens height[i] × max(i - lo, hi - i) halten, und der beste Behälter wird gezählt, wenn seine kürzere Linie an die Reihe kommt. Bei zwei gleich hohen Linien sieht die zweite platzierte die erste als Partner.

Im ersten Beispiel kommen die 7er an den Positionen 1 und 5 zuerst und halten 28. Die 6 an Position 7 sieht dann lo = 1 und hält 36. Das Sortieren benötigt O(n log n) Zeit und O(n) Speicher.

Algorithmus

Sortiere die Indizes nach Höhe, beginnend mit der größten.
Setze lo und hi auf den ersten Index dieser Reihenfolge und best auf 0.
Berechne für jeden folgenden 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 nimm an, dass height[left] ≤ height[right] gilt. Jeder andere Behälter, der die Linie left verwendet, paart sie mit einer näheren Linie, ist also schmaler und nicht höher als height[left]. Keiner davon fasst mehr Wasser als die gemessene Menge, also ist die Linie left erledigt und left rückt einen Schritt nach rechts. Bei gleicher Höhe sind beide Linien erledigt, daher ist es egal, welche du verschiebst.

Bei jedem Schritt wird eine Linie ausgemustert, sodass sich die Zeiger nach n-1 Schritten treffen. Das beste Paar wird nie übersprungen: Wenn die erste seiner beiden Linien verworfen wird, fasst der in diesem Moment gemessene Behälter mindestens genauso viel.

Im ersten Beispiel fassen die Positionen 0 und 7 insgesamt 21, und die 3 wird verworfen. Die Positionen 1 und 7 fassen 36, und die 6 wird verworfen. Die übrigen Behälter fassen 15, 28, 12, 10 und 2.

Algorithmus

Setze left = 0, right = n-1 und best = 0.
Berechne solange left < right gilt min(height[left], height[right]) × (right - left) und behalte den besten Wert bei.
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 höhere Linie verschieben. Im ersten Beispiel, das 21 statt 36 ergibt, verlässt die 6 an Position 7 die Betrachtung, 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.
Die Breite als j - i + 1 messen. Die Linien an den Positionen i und j stehen j - i auseinander, daher fasst [4, 4] 4 und nicht 8.
Annehmen, dass die Antwort die höchsten Linien 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.

Häufige Fragen3

Wie lautet 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, da jeder Schritt einen Zeiger um eine Position nach innen bewegt. Das Überprüfen aller Paare benötigt O(n²), und das Sortieren der Linien nach Höhe benötigt O(n log n).

Warum den Zeiger zur kürzeren Linie bewegen?

Das Wasser wird durch die kürzere Linie begrenzt. Jeder andere Behälter, der diese Linie beibehält, hat eine näher gelegene Gegenlinie, ist also schmaler und nicht höher. Keiner von ihnen kann den von dir gemessenen Behälter übertreffen, daher kann die kürzere Linie wegfallen, ohne dass das Ergebnis 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 dadurch ausgeschlossene Container nicht besser ist als ein bereits gemessener. Deshalb wird das Problem sowohl den Greedy-Algorithmen als auch der Zwei-Zeiger-Technik zugeordnet.

def maxArea(height):
    # Schreibe hier den Code

Test #1

Test #2

Argument

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

Erwartete Ausgabe

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 Fragen3

Ähnliche Aufgaben