Find Peak Element

Q: Wie hoch ist die Zeitkomplexität von Find Peak Element?

Die binäre Suche läuft in O(log n) Zeit und benötigt O(1) Speicherplatz, höchstens 13 Schritte bei 5000 Werten. Der Durchlauf von links ist O(n) , da er möglicherweise jedes Paar liest, bevor er den Abfall findet.

Q: Funktioniert die binäre Suche auch, wenn es mehrere Spitzen gibt?

Ja, solange benachbarte Werte unterschiedlich sind und die Stellen jenseits beider Enden als niedriger als jeder Wert gelten. Es gibt einen Spitzenwert zurück, nicht unbedingt den höchsten. Nach einem Schritt nach oben müssen die Werte spätestens am Ende des Bereichs wieder nach unten gehen, und die erste Wendung ist ein Spitzenwert, daher enthält die Seite, die die Suche beibehält, immer einen.

Q: Ist der Höchstwert immer der größte Wert?

In diesem Problem ist das so: Das Array steigt bis zu einem Gipfel an und fällt danach wieder ab, daher kann nichts anderes größer sein. In der Variante mit mehreren Gipfeln ist das nicht der Fall, da jeder Wert, der größer als seine beiden Nachbarn ist, zählt. Deshalb vergleicht die Suche die Nachbarn, statt nach dem Maximum zu suchen.

MittelBinäre Suche

+10

Das Array nums steigt zunächst an und fällt dann ab: Jeder Wert ist größer als der vorherige, bis zu einem bestimmten Index, und jeder Wert nach diesem Index ist kleiner als der vorherige. Einer der beiden Abschnitte kann leer sein, daher kann das Array auch nur ansteigen oder nur abfallen. Der Wert am Wendepunkt ist das Maximum, der einzige Wert, der größer ist als alle seine Nachbarn.

Gib den Index des Maximums in O(log n)-Zeit zurück.

Funktion

findPeakElement(nums: integer-array) → integer

numsinteger-array: die Werte, die bis zu einem einzigen Höchstwert ansteigen und dann wieder abfallen
Gibt zurückinteger: der Index des Maximums

Einschränkungen

1 ≤ nums.length ≤ 5000
-10⁶ ≤ nums[i] ≤ 10⁶
nums[i] != nums[i+1] für jedes gültige i.
nums steigt bis zu einem Index strikt an und fällt danach strikt ab, daher gibt es genau einen Gipfel.

Beispiele

Eingabe: nums = [2, 5, 9, 4, 1]
Ausgabe: 2
Erklärung: Die Werte steigen über 2, 5 und 9 an und fallen dann über 4 und 1 ab. Der Wendepunkt liegt bei 9, Index 2.

Weiterführende Frage

In einem Raster, in dem keine zwei benachbarten Zellen gleich sind, ist ein Gipfel eine Zelle, die größer ist als ihre bis zu vier Nachbarn. Kannst du einen finden, ohne jede Zelle auszulesen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Bei einem einzigen Gipfel ist der Gipfel der größte Wert, daher findet ein Durchlauf ihn in O(n). Für O(log n) vergleichst du nums[mid] mit nums[mid+1]: Die Steigung bei mid zeigt dir, auf welcher Seite des Gipfels du dich befindest, sodass du bei jedem Schritt die Hälfte des Bereichs ausschließen kannst.

Gehe weiter, bis die Werte zu sinken beginnen

Idee

Vor dem Gipfel ist jeder Wert kleiner als der nächste, und ab dem Gipfel ist jeder Wert größer. Der Gipfel ist also der erste Index i, für den nums[i] > nums[i+1] gilt, oder der letzte Index, wenn das Array nur ansteigt.

Wenn der Gipfel am Ende von 5000 Werten liegt, führt der Durchlauf 4999 Vergleiche durch, während die binäre Suche 13 benötigt.

Algorithmus

Vergleiche für i von 0 bis n-2 nums[i] mit nums[i+1].
Gib beim ersten i, bei dem nums[i] größer ist, i zurück.
Wenn die Schleife ohne einen Abfall endet, gib n-1 zurück.

def findPeakElement(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return i  # the first step down starts at the peak
    return len(nums) - 1  # never went down: the last value is the peak

Binäre Suche auf der Steigung

Idee

Lies ein Zahlenpaar, nums[mid] und nums[mid+1]. Ein Schritt nach oben bedeutet, dass das Array weiterhin ansteigt, was bei diesem Array nur vor dem Gipfel der Fall ist: Der Gipfel liegt bei mid+1 oder rechts davon. Ein Schritt nach unten bedeutet, dass du dich am Gipfel oder dahinter befindest: Der Gipfel liegt bei mid oder links davon.

Behalte einen Bereich [lo, hi] bei, der stets den Gipfel enthält. Bei einem Schritt nach oben wird lo auf mid+1 gesetzt. Bei einem Schritt nach unten wird hi auf mid gesetzt; mid bleibt erhalten, da es der Gipfel sein könnte. Wenn lo und hi zusammentreffen, ist der verbleibende Index der Gipfel. Durch Abrunden von mid bleibt es kleiner als hi, sodass mid+1 immer existiert.

Im ersten Beispiel ergibt mid = 2 den Vergleich 9 > 4, also hi = 2; dann ergibt mid = 1 den Vergleich 5 < 9, also lo = 2, den Gipfel. 5000 Werte benötigen höchstens 13 Schritte.

Algorithmus

Setze lo = 0 und hi = n-1.
Solange lo < hi gilt, berechne mid = lo + (hi - lo) / 2 und runde ab.
Wenn nums[mid] < nums[mid+1] gilt, setze lo = mid + 1.
Andernfalls setze hi = mid.
Gib lo zurück.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1  # the peak is always inside [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2  # mid < hi, so mid + 1 is a valid index
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1  # still climbing: the peak is to the right of mid
        else:
            hi = mid  # going down: the peak is mid or to its left
    return lo

Stolperfallen und Grenzfälle

hi = mid - 1 bei einem Abwärtsschritt setzen. In [2, 5, 9, 4, 1] ist das erste mid selbst der Gipfel, und hi = 1 verwirft ihn; die Suche gibt 1 zurück.
Mit nums[mid-1] vergleichen, während mid abgerundet wird. mid kann 0 sein; dort gibt es keinen linken Nachbarn.
Einen halboffenen Bereich mit hi = n verwenden. Dann kann mid n-1 sein, und nums[mid+1] greift über das Ende hinaus – sogar bei nur einem Wert.
Die Verschiebung in Lua und R vergessen. Die Antwort ist weiterhin der 0-basierte Index, daher wird eine Position i als i-1 zurückgegeben.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Find Peak Element?

Die binäre Suche läuft in O(log n) Zeit und benötigt O(1) Speicherplatz, höchstens 13 Schritte bei 5000 Werten. Der Durchlauf von links ist O(n), da er möglicherweise jedes Paar liest, bevor er den Abfall findet.

Funktioniert die binäre Suche auch, wenn es mehrere Spitzen gibt?

Ja, solange benachbarte Werte unterschiedlich sind und die Stellen jenseits beider Enden als niedriger als jeder Wert gelten. Es gibt einen Spitzenwert zurück, nicht unbedingt den höchsten. Nach einem Schritt nach oben müssen die Werte spätestens am Ende des Bereichs wieder nach unten gehen, und die erste Wendung ist ein Spitzenwert, daher enthält die Seite, die die Suche beibehält, immer einen.

Ist der Höchstwert immer der größte Wert?

In diesem Problem ist das so: Das Array steigt bis zu einem Gipfel an und fällt danach wieder ab, daher kann nichts anderes größer sein. In der Variante mit mehreren Gipfeln ist das nicht der Fall, da jeder Wert, der größer als seine beiden Nachbarn ist, zählt. Deshalb vergleicht die Suche die Nachbarn, statt nach dem Maximum zu suchen.

def findPeakElement(nums):
    # Schreibe hier Code

Test #1

Test #2

Test #3

Argument

nums = [2, 5, 9, 4, 1]

Erwartete Ausgabe