Maximum im Sliding Window mit Deque
Halten Sie die Extremwerte des Fensters in O(n) vor
Maximum im Sliding Window mit Deque ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das Maximum im gleitenden Fenster
Gegeben sind ein Array und eine Fenstergröße k. Sie möchten das Maximum jedes Fensters bestimmen, während es nach rechts gleitet. Naiv würde das O(n · k) benötigen.
Ein schnelleres Versprechen
Mit einer monotonen deque können Sie jedes Fenster in insgesamt O(n) Zeit verarbeiten, indem Sie das Array nur einmal durchlaufen.
Wieder Indizes speichern
Speichern Sie Indizes in der deque, nicht die Werte. Anhand der Indizes können Sie prüfen, ob das vorderste Element aus dem aktuellen Fenster herausgeschoben wurde.
from collections import deque
dq = deque()
res = []Absteigende Reihenfolge beibehalten
Die deque bleibt von vorne nach hinten nach Werten absteigend sortiert. Daher zeigt der vorderste Index immer auf das Maximum des Fensters.
Kleinere Enden entfernen
Entfernen Sie vor dem Hinzufügen des Index i so lange Elemente vom Ende, wie deren Werte kleiner sind, da sie niemals ein künftiges Maximum sein können.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Den neuen Index anhängen
Nachdem Sie die schwächeren Elemente am Ende entfernt haben, hängen Sie den aktuellen Index an. Die Reihenfolge der deque bleibt für die nächsten Schritte korrekt.
dq.append(i)Das veraltete vordere Element entfernen
Wenn der vorderste Index außerhalb des Fensters liegt, entfernen Sie ihn mit popleft. Ein Fenster der Größe k beginnt bei Index i minus k plus eins.
if dq[0] <= i - k:
dq.popleft()Jedes Maximum eintragen
Sobald sich bei Index k minus eins das erste vollständige Fenster bildet, enthält der Anfang der deque für jede folgende Position die Antwort.
if i >= k - 1:
res.append(nums[dq[0]])Auf die Reihenfolge beim Entfernen achten
Entfernen Sie das veraltete vordere Element, bevor Sie die Antwort auslesen. Andernfalls könnten Sie ein Maximum melden, das das Fenster bereits verlassen hat.
Warum die Laufzeit linear bleibt
Jeder Index wird höchstens einmal hinzugefügt und einmal entfernt. Daher beträgt die Arbeit der deque amortisiert O(1) pro Schritt und insgesamt O(n).
Minimum im Fenster, dieselbe Idee
Für das gleitende Fenster-Minimum halten Sie die deque stattdessen aufsteigend. Kehren Sie beim Kürzen des Endes einfach den Vergleich um.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Kurzprüfung
Was enthält der Anfang der monotonen deque beim Maximum eines gleitenden Fensters?
Zusammenfassung: Deque gewinnt beim Fenster
Sie haben eine absteigende deque aus Indizes verwendet: Entfernen Sie kleine Elemente am Ende, entfernen Sie das veraltete vordere Element und lesen Sie für jedes FenstermMaximum den Anfang in O(n) aus. 🏆
Häufig gestellte Fragen
Ist die Lektion „Maximum im Sliding Window mit Deque“ kostenlos?
Ja — der vollständige Text von „Maximum im Sliding Window mit Deque“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Maximum im Sliding Window mit Deque“?
Halten Sie die Extremwerte des Fensters in O(n) vor Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Maximum im Sliding Window mit Deque“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Stapel zum Abgleichen von Klammern
- Monotoner Stapel: nächstgrößeres Element
- Warteschlangen und collections.deque
- Maximum im Sliding Window mit Deque