Sliding-Window-Maximum mit monotoner Deque
Verwalten Sie eine absteigende Deque von Indizes, um Maximum-in-Fenster-Abfragen pro Element in O(1) zu beantworten und das Problem sliding-window-maximum in O(n) zu lösen.
Sliding-Window-Maximum mit monotoner Deque ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 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 DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Problem: Maximum im Gleitfenster
Beim Problem Maximum im Gleitfenster (LeetCode 239) werden ein Array und eine Fenstergröße k vorgegeben. Wenn das Fenster sich Schritt für Schritt von links nach rechts bewegt, geben Sie für jedes Fenster das größte Element aus. Ein Brute-Force-Ansatz berechnet das Maximum jedes Fensters mit k Elementen in O(k) – insgesamt ergibt das O(nk), was für große k zu langsam ist.
Die Lösung mit einer monotonen Deque (doppelt endende Warteschlange) erreicht insgesamt O(n), indem sie eine absteigende Deque mit Indizes verwaltet. Am Anfang steht immer der Index des Maximums im aktuellen Fenster. Dadurch sind Maximumsabfragen in O(1) möglich, während Operationen an beiden Enden unterstützt werden.
from collections import deque
# Brute force O(nk) for comparison
def sliding_max_brute(nums, k):
return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print('Input:', nums, 'k=', k)
print('Expected: [3, 3, 5, 5, 6, 7]')
print('Brute: ', sliding_max_brute(nums, k))Monotone Deque: Die Grundidee
Verwalten Sie eine monoton absteigende Deque, die Indizes (keine Werte) speichert. Die Invariante lautet: nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[-1]]. Bevor Sie den Index i hinzufügen:
- Entfernen Sie abgelaufene Indizes am Anfang: Wenn
deque[0] <= i - kgilt, hat der Index das Fenster verlassen. - Entfernen Sie Indizes mit kleineren Werten am Ende: Solange
nums[deque[-1]] <= nums[i]gilt, können diese Indizes niemals das Maximum eines zukünftigen Fensters sein (sie liegen weiter links und haben einen kleineren Wert). Verwerfen Sie sie daher.
Fügen Sie i nach diesen Operationen am Ende ein. Am Anfang steht immer das Maximum des aktuellen Fensters.
from collections import deque
def sliding_window_max(nums, k):
dq = deque() # stores indices; values are decreasing
result = []
for i, n in enumerate(nums):
# 1. Remove indices outside the current window
while dq and dq[0] <= i - k:
dq.popleft()
# 2. Remove indices with smaller values from the back
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
# 3. Record max when first full window is complete
if i >= k - 1:
result.append(nums[dq[0]]) # front = max of current window
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3)) # [3, 3, 5, 5, 6, 7]Die Deque Schritt für Schritt nachverfolgen
Verfolgen wir [1, 3, -1, -3, 5, 3, 6, 7] mit k=3:
- i=0 (1): dq=[0]
- i=1 (3): pop 0 (1<3), dq=[1]
- i=2 (-1): -1<3, daher behalten, dq=[1,2]. Fenster [1,3,-1], max=nums[1]=3
- i=3 (-3): -3<-1, dq=[1,2,3]. Vorderes Element prüfen: 1 > 3-3=0, OK. Maximum des Fensters=3
- i=4 (5): pop 3,2,1 (alle kleiner), dq=[4]. Vorderes Element: 4 > 4-3=1, OK. Maximum=5
- i=5 (3): 3<5, dq=[4,5]. Vorderes Element: 4 > 5-3=2, OK. Maximum=5
- i=6 (6): pop 5,4 (beide kleiner), dq=[6]. Maximum=6
- i=7 (7): pop 6, dq=[7]. Maximum=7
from collections import deque
def sliding_window_max_trace(nums, k):
dq = deque()
result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
print(f' Remove expired index {dq[0]} from front')
dq.popleft()
while dq and nums[dq[-1]] <= n:
print(f' Remove smaller index {dq[-1]} (val={nums[dq[-1]]}) from back')
dq.pop()
dq.append(i)
print(f'i={i} n={n}: dq={list(dq)} vals={[nums[j] for j in dq]}')
if i >= k - 1:
win_max = nums[dq[0]]
result.append(win_max)
print(f' Window {nums[max(0,i-k+1):i+1]} -> max={win_max}')
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
result = sliding_window_max_trace(nums, 3)
print('Result:', result)Warum jedes Element höchstens einmal eingefügt und entfernt wird
Die O(n)-Garantie beruht auf demselben amortisierten Argument wie beim monotonen Stack: Jeder Index wird genau einmal an die Deque angehängt und höchstens einmal entfernt (entweder am Anfang, wenn er abgelaufen ist, oder am Ende, wenn er durch einen anderen Index ersetzt wird). Insgesamt gibt es in der gesamten Schleife höchstens 2n Deque-Operationen.
Die inneren While-Schleifen erhöhen die Gesamtkomplexität nicht – jeder dort ausgeführte Pop wird durch das vorherige Pushen „bezahlt“. Das ist dieselbe Überlegung wie beim monotonen Stack, erweitert auf eine Deque, die das Entfernen an beiden Enden erlaubt.
from collections import deque
def sliding_window_max_instrumented(nums, k):
dq = deque()
result = []
front_pops = back_pops = pushes = 0
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft(); front_pops += 1
while dq and nums[dq[-1]] <= n:
dq.pop(); back_pops += 1
dq.append(i); pushes += 1
if i >= k - 1:
result.append(nums[dq[0]])
print(f'n={len(nums)}: pushes={pushes}, front_pops={front_pops}, back_pops={back_pops}')
print(f'Total deque ops = {pushes + front_pops + back_pops} <= 3n = {3*len(nums)}')
return result
import random; random.seed(0)
nums = [random.randint(-100, 100) for _ in range(20)]
sliding_window_max_instrumented(nums, 5)Minimum im Gleitfenster
Das Minimum im Gleitfenster ist das symmetrische Gegenstück: Verwalten Sie eine monoton steigende Deque (entfernen Sie das letzte Element, wenn das neue Element kleiner als das letzte ist). Am Anfang steht immer das Minimum des aktuellen Fensters. Alle anderen Schritte sind mit der Maximum-Variante identisch – kehren Sie lediglich die Vergleichsrichtung um.
Aufgaben, die nach dem Minimum in einem Gleitfenster fragen, treten oft als Teilprobleme in größeren Algorithmen auf. Beispielsweise kann das Ermitteln der minimalen Kosten, um Waren entlang eines Weges mit k Zwischenstopps zu bewegen, das Minimum in einem Gleitfenster über DP-Arrays erfordern.
from collections import deque
def sliding_window_min(nums, k):
dq = deque() # increasing monotonic deque
result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft() # expired
while dq and nums[dq[-1]] >= n:
dq.pop() # pop larger values from back
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]]) # front = min
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print('Max k=3:', sliding_window_min.__name__, '->', end=' ')
print(sliding_window_min(nums, 3)) # [-1, -3, -3, -3, 3, 3]
from collections import deque
def sliding_window_max(nums, k):
dq = deque(); result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i-k: dq.popleft()
while dq and nums[dq[-1]] <= n: dq.pop()
dq.append(i)
if i >= k-1: result.append(nums[dq[0]])
return result
print('Max k=3:', sliding_window_max(nums, 3)) # [3,3,5,5,6,7]Jump Game VI: DP mit monotoner Deque
Jump Game VI (LeetCode 1696) ist ein klassisches Beispiel für die Kombination von DP und einer monotonen Deque. Gegeben sind ein Array und eine maximale Sprungweite k. Ausgehend vom Index 0 springen Sie in jedem Schritt 1 bis k Positionen weiter und addieren den Punktwert des Zielfelds. Maximieren Sie die Gesamtpunktzahl. Die DP-Rekurrenz lautet dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]). Ein Gleitfenstermaximum über das DP-Array liefert insgesamt O(n).
Dieses Muster – eine DP-Rekurrenz, bei der jede Zelle vom Maximum eines Fensters fester Größe aus vorherigen Zellen abhängt – tritt häufig auf und erfordert immer eine monotone Deque.
from collections import deque
def max_result(nums, k):
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
dq = deque([0]) # indices of max dp values in current window
for i in range(1, n):
# Remove expired indices
while dq and dq[0] < i - k:
dq.popleft()
# dp[i] = nums[i] + max dp in window [i-k, i-1]
dp[i] = nums[i] + dp[dq[0]]
# Maintain decreasing deque on dp values
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
return dp[n - 1]
print(max_result([1,-1,-2,4,-7,3], 2)) # 7: path 1->4->3
print(max_result([10,-5,-2,4,0,3], 3)) # 17: path 10->4->3
print(max_result([1,-5,-20,4,-1,3,-6,-3], 2)) # 0Maximum im Gleitfenster: Alternative mit Segmentbaum
Bei Problemen mit variabler Fenstergröße (also nicht mit einem festen k) lässt sich die monotone Deque nicht direkt einsetzen. Verwenden Sie stattdessen eine Sparse Table für statische Bereichsmaximum-Abfragen in O(1) pro Abfrage nach einer Vorverarbeitung in O(n log n) oder einen Segmentbaum für dynamische Aktualisierungen mit O(log n) pro Abfrage. Bei Gleitfenstern mit festem k ist die Deque mit O(n) jedoch unschlagbar.
Bevorzugen Sie in Vorstellungsgesprächen bei konstanter Fenstergröße immer die monotone Deque mit O(n) gegenüber dem Segmentbaum mit O(n log n). Erwähnen Sie den Zielkonflikt: Die Deque kann weder beliebige Fenstergrößen noch Aktualisierungen verarbeiten, Segmentbäume dagegen schon.
# Sparse table for static RMQ (range maximum query)
import math
def build_sparse_table(arr):
n = len(arr)
LOG = int(math.log2(n)) + 1 if n else 1
table = [[0]*n for _ in range(LOG)]
table[0] = arr[:]
j = 1
while (1 << j) <= n:
for i in range(n - (1 << j) + 1):
table[j][i] = max(table[j-1][i], table[j-1][i + (1 << (j-1))])
j += 1
return table
def query(table, l, r):
k = int(math.log2(r - l + 1))
return max(table[k][l], table[k][r - (1 << k) + 1])
arr = [1, 3, -1, -3, 5, 3, 6, 7]
table = build_sparse_table(arr)
k = 3
result = [query(table, i, i + k - 1) for i in range(len(arr) - k + 1)]
print('Sparse table result:', result) # [3, 3, 5, 5, 6, 7]Längstes Teilarray aus Einsen nach dem Löschen eines Elements
LeetCode 1493: Gegeben ist ein binäres Array. Finden Sie die Länge des längsten Teilarrays aus 1en, nachdem genau ein Element gelöscht wurde (dieses kann eine 0 oder eine 1 sein). Dies ist ein Gleitfensterproblem. Verwalten Sie ein Fenster mit höchstens einer 0. Sobald das Fenster mehr als eine 0 enthält, verkleinern Sie es von links.
Hier wird das Muster des Gleitfensters variabler Größe verwendet – keine Deque. In Kombination mit der Technik für das maximale Fenster gilt jedoch: Nachdem alle gültigen Fenster gefunden wurden, ist die maximale Länge die Antwort. Durch „ein Element löschen“ erlauben wir genau eine 0 in unserem Fenster aus 1en.
def longest_subarray(nums):
left = 0
zeros = 0
max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zeros += 1
while zeros > 1:
if nums[left] == 0:
zeros -= 1
left += 1
# Window [left, right] has at most 1 zero
# After deleting one element, length = right - left (not +1, since we delete one)
max_len = max(max_len, right - left)
return max_len
print(longest_subarray([1,1,0,1])) # 3: delete the 0
print(longest_subarray([0,1,1,1,0,1,1,0,1])) # 5
print(longest_subarray([1,1,1])) # 2: must delete one 1Vergleich von Deque, Queue und Stack
Für Vorstellungsgespräche ist es entscheidend zu verstehen, wann welcher Container verwendet wird:
- Stack (list): LIFO, Zugriff an einem Ende. Verwenden Sie ihn für DFS, das Parsen von Ausdrücken und Probleme mit monotonen Stacks.
- Queue (deque mit appendleft/popleft): FIFO, Einfügen an einem Ende, Entfernen am anderen Ende. Verwenden Sie sie für BFS und Aufgabenplanung.
- Deque: Zugriff auf beide Enden in O(1). Verwenden Sie sie für Gleitfenster mit Ablauf (Entfernen am Anfang) und monotoner Invariante (Entfernen am Ende). Das Maximum im Gleitfenster ist das klassische Deque-Problem.
Pythons collections.deque ist das Werkzeug für alle drei Strukturen. Verwenden Sie append/pop für Stack-Verhalten und append/popleft oder appendleft/pop für Queue- bzw. Deque-Verhalten.
from collections import deque
# deque as stack
stack = deque()
stack.append(1); stack.append(2); stack.append(3)
print('Stack pop:', stack.pop()) # 3 (LIFO)
# deque as queue
queue = deque()
queue.append(1); queue.append(2); queue.append(3)
print('Queue pop:', queue.popleft()) # 1 (FIFO)
# deque as sliding window with front expiry + back monotonic
dq = deque()
nums = [3, 1, 4, 1, 5, 9, 2, 6]
k = 3
for i, n in enumerate(nums):
while dq and dq[0] <= i - k: dq.popleft() # expire front
while dq and nums[dq[-1]] <= n: dq.pop() # maintain back
dq.append(i)
if i >= k - 1:
print(f'Window {nums[max(0,i-k+1):i+1]}: max={nums[dq[0]]}')Kürzestes Teilarray mit einer Summe von mindestens K: Deque + Präfixsummen
Kürzestes Teilarray mit einer Summe von mindestens K (LeetCode 862) ist ein anspruchsvolles Problem, das Präfixsummen mit einer monotonen Deque kombiniert. Erstellen Sie Präfixsummen und verwenden Sie anschließend eine Deque, um für jeden rechten Endpunkt die am weitesten links liegende Präfixsumme zu finden, die prefix[right] - prefix[left] >= k erfüllt. Die Deque verwaltet aufsteigende Präfixsummen (entfernt Elemente am Ende, um die aufsteigende Reihenfolge beizubehalten) und entfernt Elemente am Anfang, um gültige Antworten zu erfassen.
Dies ist eines der schwierigsten Gleitfensterprobleme, weil negative Zahlen vorkommen (wodurch ein einfaches Zwei-Zeiger-Verfahren ausgeschlossen wird) und die Deque sowohl als monotone Struktur als auch als Ablaufmechanismus dienen muss.
from collections import deque
def shortest_subarray(nums, k):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
dq = deque() # monotonic increasing deque of indices into prefix
result = float('inf')
for right in range(n + 1):
# Pop from front: valid subarrays ending at `right`
while dq and prefix[right] - prefix[dq[0]] >= k:
result = min(result, right - dq.popleft())
# Pop from back: maintain increasing deque
while dq and prefix[dq[-1]] >= prefix[right]:
dq.pop()
dq.append(right)
return result if result != float('inf') else -1
print(shortest_subarray([1], 1)) # 1
print(shortest_subarray([1, 2], 4)) # -1
print(shortest_subarray([2, -1, 2], 3)) # 3
print(shortest_subarray([84,-37,32,40,95], 167)) # 3Strategie für Deque-Aufgaben in Vorstellungsgesprächen
Erkennen Sie ein Problem für eine monotone Deque an diesen Hinweisen: (1) Sie benötigen das Maximum oder Minimum eines Gleitfensters fester Größe, (2) Sie benötigen eine DP-Rekurrenz dp[i] = f(nums[i], max(dp[i-k..i-1])) oder (3) Sie benötigen den nächsten gültigen Index, der eine monotone Bedingung erfüllt.
Implementieren Sie die Deque im Vorstellungsgespräch klar und sauber: Importieren Sie deque, verwalten Sie die beiden Invarianten (Ablauf am Anfang, Monotonie am Ende) und geben Sie Ergebnisse ab dem Index k-1 zurück. Nennen Sie immer die Zeitkomplexität O(n) und den Speicherbedarf O(k) für die Deque (höchstens k gespeicherte Indizes gleichzeitig) und vergleichen Sie die Lösung mit der Brute-Force-Komplexität O(nk), um die Verbesserung zu zeigen.
from collections import deque
# Clean, interview-ready template
def sliding_window_max_template(nums, k):
if not nums or k == 0:
return []
dq = deque() # monotonic decreasing, stores indices
result = []
for i in range(len(nums)):
# Invariant 1: remove expired indices (outside window)
while dq and dq[0] < i - k + 1:
dq.popleft()
# Invariant 2: remove indices with smaller values (useless)
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# Record result once first full window is established
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Complexity: O(n) time, O(k) space
print(sliding_window_max_template([1,3,-1,-3,5,3,6,7], 3))
print(sliding_window_max_template([1], 1))
print(sliding_window_max_template([], 3))Schnelltest
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Eine monoton absteigende Deque hält das Maximum des Fensters an ihrem Anfang und verwirft am Ende Elemente, die kleiner als neu hinzukommende Elemente sind, abgelaufene Indizes werden am Anfang entfernt, sobald sie außerhalb der Fenstergrenze liegen, und jeder Index wird höchstens einmal eingefügt und entfernt, was insgesamt O(n) bei einem Deque-Speicherbedarf von O(k) ergibt. Als Nächstes lösen wir das Problem des Regenwasserauffangens mit dem monotonen Stack und dem Zwei-Zeiger-Verfahren.
Häufig gestellte Fragen
Ist die Lektion „Sliding-Window-Maximum mit monotoner Deque“ kostenlos?
Ja — der vollständige Text von „Sliding-Window-Maximum mit monotoner 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 DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Sliding-Window-Maximum mit monotoner Deque“?
Verwalten Sie eine absteigende Deque von Indizes, um Maximum-in-Fenster-Abfragen pro Element in O(1) zu beantworten und das Problem sliding-window-maximum in O(n) zu lösen. Du übst DSA 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 DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA 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 3 von 4.
Wie lange dauert die Lektion „Sliding-Window-Maximum mit monotoner 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 DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA 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
- Monotoner Stack: aufsteigend vs. absteigend
- Größtes Rechteck im Histogramm
- Sliding-Window-Maximum mit monotoner Deque
- Trapping Rain Water: Stack und Zwei-Zeiger