Sliding Window Maximum

Q: Wie hoch ist die Zeitkomplexität des Sliding Window Maximum?

Die Lösung mit der monotonen Deque läuft in O(n) Zeit. Jeder Index wird einmal eingefügt und höchstens einmal entfernt, sodass die innere Schleife über den gesamten Ablauf höchstens n Elemente entfernt, auch wenn in einem einzelnen Schritt mehrere entfernt werden können. Die Deque enthält höchstens k Indizes, daher beträgt der zusätzliche Speicherplatz zusätzlich zum Ergebnis O(k) .

SchwerSliding Window Monotoner Stack Warteschlange

+10

Du erhältst ein Array von ganzen Zahlen nums und eine Fenstergröße k. Ein Fenster umfasst k aufeinanderfolgende Werte. Es beginnt am linken Ende des Arrays und bewegt sich jeweils um eine Position nach rechts, bis seine rechte Kante beim letzten Wert liegt.

Gib ein Array mit dem größten Wert innerhalb des Fensters an jeder seiner Positionen von links nach rechts zurück. Ein Array der Länge n hat n-k+1 Fenster, daher enthält das Ergebnis n-k+1 Werte.

Funktion

maxSlidingWindow(nums: integer-array, k: integer) → integer-array

numsinteger-array: das Array, über das das Fenster gleitet
kinteger: die Anzahl der Werte in jedem Fenster
Gibt zurückinteger-array: der größte Wert jedes Fensters, vom linkesten Fenster bis zum rechtesten

Einschränkungen

1 ≤ k ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Das Ergebnis enthält nums.length-k+1 Werte, einen pro Fenster, von links nach rechts angeordnet.

Beispiele

Eingabe: nums = [4, 2, 12, 3, 8, 5, 1]k = 3
Ausgabe: [12, 12, 12, 8, 8]
Erklärung: 12 befindet sich in den ersten drei Fenstern: [4, 2, 12], [2, 12, 3] und [12, 3, 8]. Nachdem es herausgeschoben wurde, ist 8 in den Fenstern [3, 8, 5] und [8, 5, 1] jeweils der größte Wert.

Eingabe: nums = [-3, -1, -7, -2]k = 2
Ausgabe: [-1, -1, -2]
Erklärung: Die Fenster sind [-3, -1], [-1, -7] und [-7, -2]. Die größte von zwei negativen Zahlen ist diejenige, die näher an null liegt. Daraus ergeben sich -1, -1 und -2.

Eingabe: nums = [6, 6, 1]k = 3
Ausgabe: [6]
Erklärung: Wenn k der Länge des Arrays entspricht, gibt es ein Fenster: das gesamte Array. Sein größter Wert ist 6, und das zweite Vorkommen von 6 ergibt keine zweite Antwort.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du eine Warteschlange erstellen, die in amortisierter Zeit von jeweils O(1) das Hinzufügen eines Werts am Ende, das Entfernen des Werts am Anfang und das Auslesen ihres aktuellen Maximums unterstützt?

Tipps

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

0 von 3 geöffnet

Lösung

Benachbarte Fenster teilen sich k-1 Werte, sodass die Berechnung jedes Maximums von Grund auf fast die gesamte Arbeit wiederholt. Der schwierige Teil ist, dass sich ein Maximum nicht rückgängig machen lässt: Wenn der größte Wert links herausgleitet, brauchst du den nächstgrößten, ohne das Fenster erneut zu durchlaufen. Eine monotone Deque enthält der Reihenfolge nach genau die Werte, die noch zum Maximum werden könnten. So steht die Antwort immer an ihrer Spitze und jeder Index wird genau einmal eingefügt und entfernt.

Jedes Fenster durchsuchen

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

Idee

Der naheliegendste Ansatz ergibt sich aus der Aufgabenstellung. Das Fenster, das am Index start beginnt, umfasst die Werte von start bis start+k-1. Lies diese k Werte aus, behalte den größten und verschiebe den Start um einen Schritt nach rechts. Es gibt n-k+1 Startpositionen, von 0 bis n-k.

Der Ansatz ist per Definition korrekt: Jedes Fenster wird vollständig durchlaufen, sodass sein größter Wert nicht übersehen werden kann. Der zusätzliche Speicherbedarf beträgt eine Variable für das laufende Maximum, abgesehen vom Ergebnis.

Der Ansatz ist langsam. Jedes der n-k+1 Fenster erfordert k Lesezugriffe, und das Produkt ist am größten, wenn k ungefähr der Hälfte von n entspricht. Bei n = 2 × 10^4 und k = 10^4 sind das 10^4 Fenster mit jeweils 10^4 Werten, also 10^8 Lesezugriffe. Schlimmer noch: Zwei benachbarte Fenster haben k-1 Werte gemeinsam, sodass fast jeder Lesezugriff einen Wert erneut liest, den du bereits ausgelesen hast.

Algorithmus

Erstelle eine leere Ergebnisliste.
Durchlaufe start von 0 bis n-k.
Setze best auf nums[start], vergleiche es dann mit jedem Wert bis einschließlich nums[start+k-1] und behalte den größeren Wert.
Füge best zum Ergebnis hinzu.
Gib das Ergebnis zurück.

def maxSlidingWindow(nums, k):
    result = []
    for start in range(len(nums) - k + 1):
        # Read all k values of this window again
        result.append(max(nums[i] for i in range(start, start + k)))
    return result

Blöcke mit Maximalwerten von jeder Seite

Idee

Teile das Array in Blöcke der Länge k auf: Indizes 0 bis k-1, dann k bis 2k-1 und so weiter; falls n kein Vielfaches von k ist, ist der letzte Block kürzer. Ein Fenster ist genau k Elemente lang und entspricht daher entweder einem Block oder umfasst das Ende eines Blocks und den Anfang des nächsten. Es berührt niemals drei Blöcke.

Das legt zwei Arrays nahe. fromStart[i] ist der größte Wert vom Anfang des Blocks von i bis einschließlich i; die Werte werden von links nach rechts berechnet und an jedem Blockanfang zurückgesetzt. toEnd[i] ist der größte Wert von i bis zum Ende seines Blocks; die Werte werden von rechts nach links berechnet und an jedem Blockende zurückgesetzt. Das bei i beginnende Fenster endet bei i+k-1. Sein linker Teil wird von toEnd[i] und sein rechter Teil von fromStart[i+k-1] abgedeckt, daher ist sein Maximum der größere der beiden Werte. Wenn das Fenster einen ganzen Block umfasst, ist das Maximum beider Teile das Maximum dieses Blocks, und die Antwort ist weiterhin korrekt.

Bei nums = [4, 2, 12, 3, 8, 5, 1] und k = 3 sind die Blöcke [4, 2, 12], [3, 8, 5] und [1]. fromStart ist [4, 4, 12, 3, 8, 8, 1] und toEnd ist [12, 12, 12, 8, 8, 5, 1]. Das Fenster [2, 12, 3] beginnt bei 1: toEnd[1] = 12 deckt 2 und 12 ab, fromStart[3] = 3 deckt 3 ab, und die Antwort ist 12.

Dies läuft in O(n) Zeit und benötigt drei Durchläufe über das Array. Der Nachteil sind zwei Hilfsarrays der Länge n; außerdem muss das gesamte Array vorliegen, bevor das erste Fenster ausgewertet werden kann.

Algorithmus

Fülle fromStart von links nach rechts: Kopiere nums[i], wenn i ein Vielfaches von k ist, andernfalls nimm den größeren Wert von fromStart[i-1] und nums[i].
Fülle toEnd von rechts nach links: Kopiere nums[i], wenn i der letzte Index ist oder i+1 ein Vielfaches von k ist, andernfalls nimm den größeren Wert von toEnd[i+1] und nums[i].
Füge für jeden Startwert i von 0 bis n-k den größeren Wert von toEnd[i] und fromStart[i+k-1] hinzu.
Gib das Ergebnis zurück.

def maxSlidingWindow(nums, k):
    n = len(nums)
    # Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
    from_start = [0] * n  # max from the start of i's block up to i
    to_end = [0] * n      # max from i up to the end of i's block
    for i in range(n):
        if i % k == 0:
            from_start[i] = nums[i]
        else:
            from_start[i] = max(from_start[i - 1], nums[i])
    for i in range(n - 1, -1, -1):
        if i == n - 1 or (i + 1) % k == 0:
            to_end[i] = nums[i]
        else:
            to_end[i] = max(to_end[i + 1], nums[i])
    # A window [i, i+k-1] is the tail of one block plus the head of the next.
    return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]

Monotone Deque von Indizes

Idee

Gehe von einer Beobachtung aus. Angenommen, Index j kommt vor Index i und nums[j] ≤ nums[i]. Jedes spätere Fenster, das j noch enthält, enthält auch i, denn i liegt weiter rechts und verlässt das Fenster später. In all diesen Fenstern ist nums[i] mindestens genauso groß, also kann j nie wieder das Maximum sein. Sobald i eintrifft, ist j nutzlos und du kannst es vergessen.

Verwende eine doppelseitige Warteschlange mit den Indizes, die du noch nicht vergessen hast. Wenn i eintrifft, entferne hinten so lange Indizes, deren Werte höchstens nums[i] sind, und füge dann i hinzu. Die verbleibenden Werte sind dann von vorne nach hinten streng absteigend, denn jeder ältere Wert, der nicht größer war, wäre entfernt worden. Somit steht vorne der größte Wert im Fenster. Die Deque speichert Indizes und nicht Werte, weil auch der vorderste Eintrag entfernt werden muss, wenn das Fenster über ihn hinweggleitet: Das Fenster, das bei i endet, beginnt bei i-k+1, also ist Index i-k der herausgeglittene Eintrag; steht er vorne, entfernst du ihn.

Verfolge nums = [4, 2, 12, 3, 8, 5, 1] mit k = 3 und liste die Werte in der Deque auf. 4 kommt hinzu: [4]. 2 ist kleiner und kommt daher dahinter: [4, 2]. 12 entfernt beide: [12], und die Antwort für das erste Fenster ist 12. 3 kommt hinzu: [12, 3], Antwort 12. 8 entfernt 3: [12, 8], Antwort 12. 5 kommt hinzu: [12, 8, 5], aber 12 steht an Index 2, und das Fenster, das bei Index 5 endet, beginnt bei Index 3. 12 ist also herausgeglitten: [8, 5], Antwort 8. 1 kommt hinzu: [8, 5, 1], Antwort 8.

Warum das O(n) ist: Die innere Schleife kann in einem Schritt mehrere Indizes entfernen, aber jeder Index wird einmal hinzugefügt und höchstens einmal entfernt – entweder hinten, wenn ein größerer Wert ihn übertrifft, oder vorne, wenn er herausgleitet. Insgesamt werden höchstens n Einträge entfernt, also gibt es höchstens 2n Deque-Operationen. Jeder Index in der Deque liegt innerhalb des aktuellen Fensters, daher enthält sie nie mehr als k Indizes.

Algorithmus

Erstelle eine leere Deque für Indizes und eine leere Ergebnisliste.
Entferne für jeden Index i Indizes vom Ende, solange die Deque nicht leer ist und der Wert am Ende höchstens nums[i] beträgt.
Füge i am Ende hinzu.
Wenn der Index am Anfang gleich i-k ist, hat er das Fenster verlassen: Entferne ihn vom Anfang.
Sobald i ≥ k-1 gilt, endet bei i ein vollständiges Fenster: Füge den Wert des Index am Anfang zum Ergebnis hinzu.
Gib das Ergebnis zurück.

from collections import deque


def maxSlidingWindow(nums, k):
    window = deque()  # indices; their values strictly decrease from front to back
    result = []
    for i, x in enumerate(nums):
        # A value at the back that is not bigger than x can never be a maximum again.
        while window and nums[window[-1]] <= x:
            window.pop()
        window.append(i)
        # The front index has slid out of the window on the left.
        if window[0] == i - k:
            window.popleft()
        # From index k-1 on, every step completes a window; its maximum sits at the front.
        if i >= k - 1:
            result.append(nums[window[0]])
    return result

Stolperfallen und Grenzfälle

Die meisten Fehler entstehen an den Rändern des Fensters oder dadurch, was die Deque speichert.

Werte statt Indizes speichern. Dann entfernst du das erste Element, wenn es gleich nums[i-k] ist, und Duplikate führen zu Fehlern. Bei [3, 1, 3] und k = 2 entfernt die zweite 3 die erste und wird dann selbst entfernt, weil sie dem Wert entspricht, der das Fenster verlassen hat. Speichere Indizes und vergleiche das erste Element mit i-k.
Zu früh oder zu spät ein Ergebnis ausgeben. Das erste vollständige Fenster endet bei Index k-1, nicht bei k, und das Ergebnis muss genau n-k+1 Werte enthalten.
Den falschen Index entfernen. Das Fenster, das bei i endet, beginnt bei i-k+1, also ist i-k der Index, der das Fenster verlässt. Wenn du i-k+1 entfernst, entfernst du einen Wert, der noch im Fenster liegt.
Das letzte oder erste Element einer leeren Deque lesen. Prüfe, ob sie ein Element enthält, bevor du es mit ihrem letzten Element vergleichst.
Die Deque als Kopie des Fensters behandeln. Sie enthält nur die Kandidaten, also zwischen 1 und k Indizes. Ihre Größe sagt daher nichts über die Größe des Fensters aus.
Beim Blockansatz vergessen, dass der letzte Block kürzer als k sein kann. Der Durchlauf von rechts nach links muss sowohl am letzten Index als auch an jedem Blockende neu beginnen.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität des Sliding Window Maximum?

Die Lösung mit der monotonen Deque läuft in O(n) Zeit. Jeder Index wird einmal eingefügt und höchstens einmal entfernt, sodass die innere Schleife über den gesamten Ablauf höchstens n Elemente entfernt, auch wenn in einem einzelnen Schritt mehrere entfernt werden können. Die Deque enthält höchstens k Indizes, daher beträgt der zusätzliche Speicherplatz zusätzlich zum Ergebnis O(k).

Kann das Maximum eines gleitenden Fensters mit einem Heap gelöst werden?

Ja. Lege Paare aus Wert und Index in einen Max-Heap. Entferne vor dem Auslesen des obersten Elements so lange das oberste Element, wie sein Index außerhalb des Fensters liegt, da veraltete Einträge erst entfernt werden, wenn sie oben angekommen sind. Das benötigt O(n log n) Zeit und kann bis zu n Einträge enthalten. Die Deque ist schneller und benötigt weniger Speicher, da sie nutzlose Werte entfernt, sobald ein größerer Wert eintrifft.

Warum speichert die Deque Indizes und keine Werte?

Das vorderste Element muss entfernt werden, wenn das Fenster darüber hinauswandert, und nur sein Index verrät dir das. Anhand der Werte allein müsstest du bei nums[i-k] raten, was fehlschlägt, wenn derselbe Wert mehr als einmal vorkommt. Der Index liefert dir außerdem kostenlos den Wert mit nums[index].

Was ist der Unterschied zwischen einer monotonen Deque und einem monotonen Stapel?

Das Ende der Deque funktioniert wie ein monotoner Stack: Bevor du einen Wert hinzufügst, entfernst du die Werte, die dadurch nutzlos werden. Die Deque hat am Anfang einen zweiten Ausgang für Werte, die zu alt sind. Ein Problem ohne Ablaufzeit, wie das Finden des nächsten größeren Elements, benötigt nur den Stack; ein gleitendes Fenster benötigt beide Enden. Kehre den Vergleich um, und derselbe Code liefert das Minimum jedes Fensters.

Python

def maxSlidingWindow(nums, k):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [4, 2, 12, 3, 8, 5, 1]
k = 3

Erwartet

[12, 12, 12, 8, 8]

Sliding Window Maximum

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Jedes Fenster durchsuchen

Blöcke mit Maximalwerten von jeder Seite

Monotone Deque von Indizes

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben