Maksimum i skydevindue med en monoton deque
Vedligehold en faldende deque af indekser for at besvare forespørgsler om maksimum i et vindue i O(1) pr. element, og løs problemet sliding-window-maximum i O(n).
Maksimum i skydevindue med en monoton deque er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Problem med maksimum i et glidende vindue
Problemet med maksimum i et glidende vindue (LeetCode 239) giver et array og en vinduesstørrelse k. Når vinduet flyttes fra venstre mod højre én position ad gangen, skal du returnere det største element i hvert vindue. En udtømmende metode beregner maksimum for hvert vindue med k elementer i O(k), hvilket giver O(nk) i alt og er for langsomt ved store k.
Løsningen med en monoton deque (dobbeltendet kø) opnår O(n) i alt ved at vedligeholde en faldende deque med indekser. Forsiden indeholder altid indekset for maksimum i det aktuelle vindue, hvilket giver forespørgsler efter maksimum i O(1), samtidig med at du kan arbejde fra både for- og bagenden.
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))Monoton deque: Den grundlæggende idé
Vedligehold en monoton faldende deque, der gemmer indekser (ikke værdier). Invarianten er: nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[-1]]. Før du tilføjer indekset i:
- Fjern udløbne indekser fra forsiden: Hvis
deque[0] <= i - k, har indekset forladt vinduet. - Fjern mindre indekser fra bagenden: Mens
nums[deque[-1]] <= nums[i], kan disse indekser aldrig være maksimum i et fremtidigt vindue (de ligger til venstre og er mindre), så fjern dem.
Efter disse operationer skal du tilføje i bagest. Forsiden giver altid maksimum i det aktuelle vindue.
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]Gennemgang af dequen trin for trin
Lad os gennemgå [1, 3, -1, -3, 5, 3, 6, 7] med k=3:
- i=0 (1): dq=[0]
- i=1 (3): pop 0 (1<3), dq=[1]
- i=2 (-1): -1<3, så beholdes den, dq=[1,2]. Vindue [1,3,-1], max=nums[1]=3
- i=3 (-3): -3<-1, dq=[1,2,3]. Tjek forsiden: 1 > 3-3=0, fint. Maksimum for vinduet=3
- i=4 (5): pop 3,2,1 (alle mindre), dq=[4]. Forside 4 > 4-3=1, fint. Maksimum=5
- i=5 (3): 3<5, dq=[4,5]. Forside 4 > 5-3=2, fint. Maksimum=5
- i=6 (6): pop 5,4 (begge mindre), dq=[6]. Maksimum=6
- i=7 (7): pop 6, dq=[7]. Maksimum=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)Hvorfor hvert element højst tilføjes og fjernes én gang
Garantien på O(n) kommer fra det samme amortiserede argument som for den monotone stak: hvert indeks tilføjes præcis én gang til dequen og fjernes højst én gang, enten fra forsiden når det udløber eller fra bagenden når det bliver erstattet. Det samlede antal operationer på dequen gennem hele løkken er højst 2n.
De indlejrede while-løkker øger ikke den samlede kompleksitet – enhver fjernelse i disse løkker er "betalt" af den tidligere tilføjelse. Det er samme ræsonnement som for den monotone stak, men udvidet til en deque, der tillader fjernelse fra begge ender.
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 i et glidende vindue
Minimum i et glidende vindue er det symmetriske modstykke: Vedligehold en monoton stigende deque (fjern fra bagenden, når det nye element er mindre end elementet bagest). Forsiden indeholder altid minimum i det aktuelle vindue. Alle øvrige trin er identiske med maksimumsvarianten – vend blot sammenligningsretningen.
Problemer, der beder om minimum i et glidende vindue, optræder ofte som delproblemer i større algoritmer. For eksempel kan minimumsomkostningen ved at flytte varer ad en sti med k mellemstop kræve minimum i et glidende vindue over DP-arrays.
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]Hopspil VI: DP med monoton deque
Hopspil VI (LeetCode 1696) er et klassisk eksempel på en kombination af DP og monoton deque. Givet et array og en maksimal springlængde k, og med start ved indeks 0, hopper du ved hvert trin 1 til k pladser frem og lægger målfeltets score til. Maksimér den samlede score. DP-recurrensen er dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]). Maksimum i et glidende vindue over DP-arrayet giver O(n) i alt.
Dette mønster – en DP-recurrens, hvor hvert felt afhænger af maksimum blandt et vindue med fast størrelse af tidligere felter – optræder ofte og kræver altid en monoton 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)) # 0Maksimum i et glidende vindue: Alternativ med segmenttræ
Til problemer, hvor vinduesstørrelsen varierer (og ikke er et fast k), kan den monotone deque ikke bruges direkte. Brug i stedet en sparse table til forespørgsler efter maksimum i statiske intervaller i O(1) pr. forespørgsel efter O(n log n) forbehandling, eller et segmenttræ til dynamiske opdateringer med O(log n) pr. forespørgsel. For glidende vinduer med fast k er dequen dog uden sidestykke med O(n).
Til jobsamtaler skal du altid foretrække den monotone deque med O(n) frem for segmenttræet med O(n log n), når vinduesstørrelsen er konstant. Nævn afvejningen: Dequen kan ikke håndtere vilkårlige vinduesstørrelser eller opdateringer, mens segmenttræer kan.
# 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ængste delarray med 1'ere efter sletning af ét element
LeetCode 1493: Givet et binært array skal du finde længden af det længste delarray med 1'ere efter sletning af præcis ét element (som kan være 0 eller 1). Dette er et problem med et glidende vindue. Vedligehold et vindue med højst én 0. Når vinduet indeholder mere end én 0, skal du indsnævre det fra venstre.
Dette bruger mønsteret med et glidende vindue af variabel størrelse – ikke en deque. Hvis du kombinerer det med teknikken for maksimale vinduer, er maksimumslængden svaret, når du har fundet alle gyldige vinduer. "Slet ét element" betyder, at vi tillader præcis én 0 i vores vindue med 1'ere.
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 1Sammenligning af deque, kø og stak
Det er afgørende for jobsamtaler at forstå, hvornår du skal bruge hver datastruktur:
- Stak (list): LIFO, adgang fra én ende. Brug den til DFS, fortolkning af udtryk og problemer med monotone stakke.
- Kø (deque med appendleft/popleft): FIFO, tilføjelse i den ene ende og fjernelse i den anden. Brug den til BFS og opgaveplanlægning.
- Deque: Begge ender kan tilgås i O(1). Brug den til glidende vinduer med udløb (fjern fra forsiden) og en monoton invariant (fjern fra bagenden). Maksimum i et glidende vindue er det klassiske deque-problem.
Python-typen collections.deque er redskabet til alle tre. Brug append/pop til stakfunktion og append/popleft eller appendleft/pop til kø- og deque-funktion.
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]]}')Korteste delarray med sum mindst K: Deque + præfikssummer
Korteste delarray med sum mindst K (LeetCode 862) er et avanceret problem, der kombinerer præfikssummer med en monoton deque. Beregn præfikssummer, og brug derefter en deque til for hvert højre slutpunkt at finde den venstre præfikssum længst mod venstre, der opfylder prefix[right] - prefix[left] >= k. Dequen vedligeholder stigende præfikssummer (fjern fra bagenden for at bevare den stigende rækkefølge) og fjerner elementer fra forsiden for at indsamle gyldige resultater.
Dette er et af de sværeste problemer med glidende vinduer, fordi det involverer negative tal (hvilket udelukker en simpel to-pointer-metode) og kræver, at dequen fungerer både som en monoton struktur og som en mekanisme til udløb.
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)) # 3Jobsamtalestrategi for deque-problemer
Genkend et problem med en monoton deque på disse tegn: (1) du har brug for maksimum eller minimum i et glidende vindue med fast størrelse, (2) du har brug for DP-recurrensen dp[i] = f(nums[i], max(dp[i-k..i-1])), eller (3) du har brug for det nærmeste gyldige indeks, der opfylder en monoton betingelse.
Til jobsamtaler skal du skrive deque-løsningen klart: importér deque, vedligehold de to invarianter (udløb fra forsiden og monotonitet fra bagenden), og returnér resultater fra og med indeks k-1. Nævn altid tidskompleksiteten O(n) og pladsforbruget O(k) for dequen (højst k indekser gemt ad gangen), og sammenlign med den udtømmende løsning O(nk) for at vise forbedringen.
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))Hurtigt tjek
Afprøv din forståelse af begreberne Data Structures & Algorithms — Coding Interview Prep fra denne lektion.
Opsummering af lektionen
I denne lektion lærte du: En monoton faldende deque holder maksimum for vinduet i forsiden, mens den kasserer elementer fra bagenden, der er mindre end nye elementer, udløbne indekser fjernes fra forsiden, når de falder uden for vinduets grænse, og hvert indeks tilføjes og fjernes højst én gang, hvilket giver O(n) i alt med O(k) plads til dequen. Nu løser vi problemet med opsamling af regnvand ved hjælp af både en monoton stak og to-pointer-metoden.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Maksimum i skydevindue med en monoton deque” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Maksimum i skydevindue med en monoton deque”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Maksimum i skydevindue med en monoton deque”?
Vedligehold en faldende deque af indekser for at besvare forespørgsler om maksimum i et vindue i O(1) pr. element, og løs problemet sliding-window-maximum i O(n). Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Maksimum i skydevindue med en monoton deque”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Monoton stak: Stigende eller faldende
- Største rektangel i et histogram
- Maksimum i skydevindue med en monoton deque
- Opsamling af regnvand: Stak og to pegere