Maximalt värde i ett glidande fönster med monoton deque
Upprätthåll en avtagande deque med index för att besvara frågor om maximum i ett fönster på O(1) per element och lös problemet sliding-window-maximum på O(n).
Maximalt värde i ett glidande fönster med monoton deque är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Problemet med maximum i ett glidande fönster
Problemet med maximum i ett glidande fönster (LeetCode 239) ger en array och en fönsterstorlek k. När fönstret flyttas från vänster till höger, en position i taget, ska du ange det största elementet i varje fönster. En brute-force-metod beräknar maximum för varje fönster med k element i O(k), vilket ger O(nk) totalt och är för långsamt för stora k.
Lösningen med en monoton deque (dubbelsidig kö) uppnår O(n) totalt genom att upprätthålla en avtagande deque med index. Framsidan innehåller alltid indexet för maximumvärdet i det aktuella fönstret, vilket ger O(1)-frågor efter maximum samtidigt som operationer i både fram- och bakkant tillåts.
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: grundidén
Upprätthåll en monoton avtagande deque som lagrar index (inte värden). Invarianten är: nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[-1]]. Innan index i läggs till:
- Ta bort utgångna index från framsidan: om
deque[0] <= i - khar indexet lämnat fönstret. - Ta bort index med mindre värden från baksidan: så länge
nums[deque[-1]] <= nums[i]kan dessa index aldrig vara maximum i något framtida fönster (de ligger till vänster och har lägre värde), så ta bort dem.
Lägg sedan till i längst bak. Framsidan ger alltid maximumvärdet för det aktuella fönstret.
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]Stegvis genomgång av dequen
Låt oss gå igenom [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 so keep, dq=[1,2]. Fönster [1,3,-1], max=nums[1]=3
- i=3 (-3): -3<-1, dq=[1,2,3]. Kontrollera framsidan: 1 > 3-3=0, OK. Fönstrets maximum=3
- i=4 (5): pop 3,2,1 (all smaller), dq=[4]. Framsidan 4 > 4-3=1, OK. Max=5
- i=5 (3): 3<5, dq=[4,5]. Framsidan 4 > 5-3=2, OK. Max=5
- i=6 (6): pop 5,4 (both smaller), dq=[6]. Max=6
- i=7 (7): pop 6, dq=[7]. Max=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)Varför varje element läggs till och tas bort högst en gång
O(n)-garantin bygger på samma amortiserade resonemang som för den monotona stacken: varje index läggs till i dequen exakt en gång och tas bort högst en gång, antingen från framsidan när det löper ut eller från baksidan när det ersätts. Det totala antalet deque-operationer i hela loopen är högst 2n.
De inre while-looparna ökar inte den totala komplexiteten — alla borttagningar som görs i dessa loopar ”betalas” av den tidigare tilläggningen. Det är samma resonemang som för den monotona stacken, men utökat till en deque som tillåter borttagning från båda ändarna.
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 glidande fönster
Minimum i glidande fönster är den symmetriska motsvarigheten: upprätthåll en monoton ökande deque (ta bort från baksidan när det nya elementet är mindre än det bakersta). Framsidan innehåller alltid minimumvärdet för det aktuella fönstret. Alla andra steg är identiska med maximumversionen — vänd bara på jämförelseriktningen.
Problem som frågar efter minimum i glidande fönster förekommer ofta som delproblem i större algoritmer. Exempelvis kan den minsta kostnaden för att flytta varor längs en väg med k mellanliggande stopp kräva minimum i glidande fönster över DP-arrayer.
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 med monoton deque
Jump Game VI (LeetCode 1696) är ett klassiskt exempel på hur DP och en monoton deque kombineras. Givet en array och en maximal hopplängd k, med start på index 0, hoppar man i varje steg 1 till k positioner framåt och lägger till målelementets poäng. Maximera totalpoängen. DP-rekurrensen är dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]). Ett maximum i glidande fönster över DP-arrayen ger O(n) totalt.
Detta mönster — en DP-rekurrens där varje cell beror på maximumvärdet i ett fönster med fast storlek av föregående celler — förekommer ofta och kräver alltid 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)) # 0Maximum i glidande fönster: alternativ med segmentträd
För problem där fönsterstorleken varierar (inte är ett fast k) kan en monoton deque inte användas direkt. Använd i stället en sparse table för statiska intervallfrågor efter maximum i O(1) per fråga efter O(n log n) förbehandling, eller ett segmentträd för dynamiska uppdateringar med O(log n) per fråga. För glidande fönster med fast k är dequen däremot oslagbar med O(n).
I intervjuer bör du alltid föredra den monotona dequen i O(n) framför segmentträdet i O(n log n) när fönsterstorleken är konstant. Nämn avvägningen: dequen kan inte hantera godtyckliga fönsterstorlekar eller uppdateringar, medan segmentträd kan göra det.
# 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ängsta delarray med ettor efter att ett element tagits bort
LeetCode 1493: givet en binär array ska du hitta längden på den längsta delarrayen med ettor efter att exakt ett element har tagits bort (det kan vara en 0:a eller en 1:a). Detta är ett problem med glidande fönster. Upprätthåll ett fönster med högst en 0:a. När fönstret innehåller fler än en 0:a krymper du det från vänster.
Detta använder mönstret med ett glidande fönster av varierande storlek — inte en deque. I kombination med maximumtekniken: när alla giltiga fönster har hittats är den största längden svaret. Att ta bort ett element innebär att vi tillåter exakt en 0:a i vårt fönster av ettor.
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 1Jämförelse mellan deque, kö och stack
Att förstå när varje behållare ska användas är viktigt i intervjuer:
- Stack (list): LIFO, åtkomst från ena änden. Används för DFS, uttrycksparsning och problem med monotona stackar.
- Kö (deque med appendleft/popleft): FIFO, tillägg i ena änden och borttagning från den andra. Används för BFS och schemaläggning av uppgifter.
- Deque: åtkomst från båda ändarna i O(1). Används för glidande fönster med utgångna element (ta bort från framsidan) och en monoton invariant (ta bort från baksidan). Maximum i glidande fönster är det klassiska deque-problemet.
Pythons collections.deque är verktyget för alla tre. Använd append/pop för stackbeteende och append/popleft eller appendleft/pop för kö- eller deque-beteende.
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]]}')Kortaste delarray med summa på minst K: deque + prefixsummor
Kortaste delarray med summa på minst K (LeetCode 862) är ett avancerat problem som kombinerar prefixsummor med en monoton deque. Beräkna prefixsummor och använd sedan en deque för att, för varje högerändpunkt, hitta den vänstraste prefixsumman som uppfyller prefix[right] - prefix[left] >= k. Dequen upprätthåller ökande prefixsummor (ta bort från baksidan för att behålla ordningen) och tar bort element från framsidan för att samla in giltiga svar.
Detta är ett av de svåraste problemen med glidande fönster eftersom det innehåller negativa tal (vilket utesluter en enkel tvåpekaralgoritm) och kräver att dequen fungerar både som en monoton struktur och som en mekanism för att ta bort utgångna element.
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)) # 3Intervjustrategi för deque-problem
Identifiera ett problem med monoton deque utifrån dessa signaler: (1) du behöver maximum eller minimum för ett glidande fönster med fast storlek, (2) du behöver DP-rekurrensen dp[i] = f(nums[i], max(dp[i-k..i-1])), eller (3) du behöver det närmaste giltiga indexet som uppfyller ett monotont villkor.
Skriv deque-lösningen rent i intervjuer: importera deque, upprätthåll de två invarianta villkoren (utgångna index i framsidan och monotonitet i baksidan), och returnera resultat från och med index k-1. Ange alltid tidskomplexiteten O(n) och utrymmeskomplexiteten O(k) för dequen (högst k index lagrade samtidigt), och jämför med brute force i O(nk) för att visa förbättringen.
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))Snabbtest
Testa dina kunskaper om begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning av lektionen
I den här lektionen har du lärt dig: en monoton avtagande deque håller maximumvärdet för fönstret längst fram samtidigt som den tar bort element från baksidan som är mindre än nya element, utgångna index tas bort från framsidan när de hamnar utanför fönstrets gräns, och varje index läggs till och tas bort högst en gång, vilket ger O(n) totalt och O(k) utrymme för dequen. Härnäst löser vi problemet med att fånga regnvatten med både en monoton stack och tvåpekar-metoden.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Maximalt värde i ett glidande fönster med monoton deque” gratis?
Ja – hela texten till ”Maximalt värde i ett glidande fönster med monoton deque” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Maximalt värde i ett glidande fönster med monoton deque”?
Upprätthåll en avtagande deque med index för att besvara frågor om maximum i ett fönster på O(1) per element och lös problemet sliding-window-maximum på O(n). Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.
Hur lång tid tar lektionen ”Maximalt värde i ett glidande fönster med monoton deque”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Monoton stack: ökande eller minskande
- Största rektangeln i ett histogram
- Maximalt värde i ett glidande fönster med monoton deque
- Trapping Rain Water: stack och två pekare