Die Zwei-Zeiger-Technik

Containerbereich mit zwei Zeigern in Go maximieren

In Algorithmen, die mit Arrays oder Listen arbeiten, zeichnet sich die Zwei-Zeiger-Technik durch ihre Effizienz aus. In diesem Artikel wenden wir es auf das klassische Problem „Behälter mit dem meisten Wasser“ an, bei dem die größte Fläche zwischen zwei vertikalen Linien in einem Diagramm gesucht wird.

Problembeschreibung

Suchen Sie anhand eines Arrays nicht negativer Ganzzahlen, die die Höhen vertikaler Linien darstellen, das Linienpaar, das zusammen mit der x-Achse den Container mit der größten Fläche bildet.

Beispiel

Betrachten Sie das Array height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. Das Ziel besteht darin, zu bestimmen, welche zwei Linien die maximale Fläche erzeugen.

Zwei-Punkte-Technik

Die Technik verwendet zwei Zeiger, einen am Anfang und einen am Ende des Arrays, und bewegt sie iterativ in Richtung der Mitte, um die optimale Lösung zu finden.

Schritt für Schritt

1. Startup:

   • maxArea wird auf 0 initialisiert und speichert den größten bisher gefundenen Bereich.
   • Zwei Zeiger, l (links) und r (rechts), werden am Anfang bzw. Ende des Arrays positioniert.

2. Iteration:

   • Die Schleife wird fortgesetzt, solange l kleiner als r ist.
   • Die Fläche zwischen den Linien in l und r wird als min(height[l], height[r]) * (r - l) berechnet.
   • maxArea wird aktualisiert, wenn die berechnete Fläche größer ist.

3. Bewegung der Zeiger:

   • Um die Suche zu optimieren, wird der Zeiger, der auf die kleinere Linie zeigt, verschoben:
     • Wenn height[l] < height[r], erhöhen Sie l.
     • Andernfalls verringern Sie r.

4. Rückgabe:

   • Wenn l und r sich schneiden, endet die Schleife und maxArea enthält die maximale Fläche.

Detailliertes Beispiel

Lassen Sie uns das Array analysieren height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

1. Startup:

   • maxArea = 0
   • l = 0 (Höhe 1), r = 8 (Höhe 7)

2. Erste Iteration:

   • Bereich: min(1, 7) * (8 - 0) = 8
   • maxArea = max(0, 8) = 8
   • Verschieben l (weil height[l] < height[r])

3. Zweite Iteration:

   • l = 1 (Höhe 8), r = 8 (Höhe 7)
   • Bereich: min(8, 7) * (8 - 1) = 49
   • maxArea = max(8, 49) = 49
   • Verschieben r

...und so weiter, wobei der Vorgang wiederholt wird, bis sich die Hände treffen.

Das Endergebnis wird maxArea = 49 sein.

Go-Lösung

Folgen Sie dem Go-Code, der die Technik implementiert:

package maxarea

func maxArea(height []int) int {
    maxArea := 0
    l, r := 0, len(height)-1

    for l < r {
        area := min(height[l], height[r]) * (r - l)
        maxArea = max(maxArea, area)
        if height[l] < height[r] {
            l++
        } else {
            r--
        }
    }
    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Fazit

Die Zwei-Zeiger-Technik bietet eine effiziente Lösung für Probleme mit Arrays. Im Fall von „Container With Most Water“ garantiert es eine lineare Zeitkomplexität und ist somit ein idealer Ansatz.

Das obige ist der detaillierte Inhalt vonDie Zwei-Zeiger-Technik. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!