Massimo in una finestra scorrevole con deque monotona
Mantenga una deque decrescente di indici per rispondere alle query del massimo nella finestra in O(1) per elemento, risolvendo il problema sliding-window-maximum in O(n).
Massimo in una finestra scorrevole con deque monotona è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Problema del massimo su una finestra scorrevole
Il problema Sliding Window Maximum (LeetCode 239) presenta un array e una dimensione k della finestra. Mentre la finestra scorre da sinistra a destra, una posizione alla volta, restituisca l'elemento massimo di ogni finestra. Un approccio a forza bruta calcola il massimo di ogni finestra di k elementi in O(k), ottenendo un totale di O(nk), troppo lento per valori elevati di k.
La soluzione con una deque monotona (coda a doppia estremità) raggiunge O(n) complessivo mantenendo una deque decrescente di indici. Il fronte contiene sempre l'indice del massimo nella finestra corrente, fornendo query del massimo in O(1) e consentendo operazioni sia sul fronte sia sul fondo.
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))Deque monotona: l'idea chiave
Mantenga una deque decrescente monotona che memorizza indici (non valori). L'invariante è: nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[-1]]. Prima di aggiungere l'indice i:
- Rimuova gli indici scaduti dal fronte: se
deque[0] <= i - k, l'indice è uscito dalla finestra. - Rimuova dal fondo gli indici con valori più piccoli: finché
nums[deque[-1]] <= nums[i], tali indici non potranno mai essere il massimo di una finestra futura (si trovano più a sinistra e hanno un valore minore), quindi li scarti.
Dopo queste operazioni, inserisca i in fondo. Il fronte fornisce sempre il massimo della finestra corrente.
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]Tracciamento della deque passo dopo passo
Tracciamo [1, 3, -1, -3, 5, 3, 6, 7] con k=3:
- i=0 (1): dq=[0]
- i=1 (3): pop 0 (1<3), dq=[1]
- i=2 (-1): -1<3, quindi si conserva, dq=[1,2]. Finestra [1,3,-1], max=nums[1]=3
- i=3 (-3): -3<-1, dq=[1,2,3]. Controllo del fronte: 1 > 3-3=0, OK. Massimo della finestra=3
- i=4 (5): pop 3,2,1 (tutti più piccoli), dq=[4]. Il fronte 4 > 4-3=1, OK. Max=5
- i=5 (3): 3<5, dq=[4,5]. Il fronte 4 > 5-3=2, OK. Max=5
- i=6 (6): pop 5,4 (entrambi più piccoli), 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)Perché ogni elemento viene inserito ed estratto al massimo una volta
La garanzia di O(n) deriva dallo stesso argomento ammortizzato dello stack monotono: ogni indice viene aggiunto alla deque esattamente una volta e rimosso (dal fronte quando scade oppure dal fondo quando viene sostituito) al massimo una volta. Le operazioni totali sulla deque durante l'intero ciclo sono al massimo 2n.
I cicli while interni non aumentano la complessità complessiva: ogni estrazione eseguita in questi cicli è 'pagata' dall'inserimento precedente. È lo stesso ragionamento dello stack monotono, esteso però a una deque che consente la rimozione da entrambe le estremità.
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)Minimo su una finestra scorrevole
Il minimo su una finestra scorrevole è la controparte simmetrica: mantenga una deque crescente monotona (estragga dal fondo quando il nuovo elemento è minore dell'ultimo). Il fronte contiene sempre il minimo della finestra corrente. Ogni altro passaggio è identico alla versione del massimo: basta invertire la direzione del confronto.
I problemi che richiedono il minimo su una finestra scorrevole compaiono spesso come sottoproblemi all'interno di algoritmi più grandi. Per esempio, il costo minimo per spostare merci lungo un percorso con k fermate intermedie può richiedere il minimo su una finestra scorrevole applicato ad array DP.
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 con una deque monotona
Jump Game VI (LeetCode 1696) è un esempio classico di combinazione tra DP e deque monotona. Dato un array e una lunghezza massima del salto k, partendo dall'indice 0, a ogni passaggio salti da 1 a k posizioni in avanti, aggiungendo il punteggio della cella di destinazione. Massimizzi il punteggio totale. La ricorrenza DP è dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]). Un massimo su una finestra scorrevole applicato all'array DP fornisce un tempo totale O(n).
Questo schema — una ricorrenza DP in cui ogni cella dipende dal massimo di una finestra di dimensione fissa delle celle precedenti — compare frequentemente e richiede sempre una deque monotona.
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)) # 0Massimo su una finestra scorrevole: alternativa con un albero di segmenti
Per i problemi in cui la dimensione della finestra varia (non è un k fisso), la deque monotona non si applica direttamente. Utilizzi invece una tabella sparsa per query statiche del massimo su intervalli in O(1) per query dopo una preelaborazione O(n log n), oppure un albero di segmenti per aggiornamenti dinamici con O(log n) per query. Tuttavia, per le finestre scorrevoli con k fisso, la deque è imbattibile con O(n).
Durante i colloqui, preferisca sempre la deque monotona O(n) all'albero di segmenti O(n log n) quando la dimensione della finestra è costante. Menzioni il compromesso: la deque non può gestire dimensioni arbitrarie della finestra né aggiornamenti, mentre gli alberi di segmenti possono farlo.
# 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]Sottoarray più lungo di uni dopo aver eliminato un elemento
LeetCode 1493: dato un array binario, trovi la lunghezza del sottoarray più lungo composto da 1 dopo aver eliminato esattamente un elemento (che può essere uno 0 o un 1). Questo è un problema di finestra scorrevole. Mantenga una finestra con al massimo uno 0. Quando la finestra contiene più di uno 0, la riduca dal lato sinistro.
Qui si utilizza il modello della finestra scorrevole di dimensione variabile, non una deque. Tuttavia, combinandolo con la tecnica della finestra di lunghezza massima, dopo aver trovato tutte le finestre valide la lunghezza massima è la risposta. L'operazione 'eliminare un elemento' significa consentire esattamente uno 0 nella finestra di 1.
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 1Confronto tra deque, coda e stack
Capire quando utilizzare ciascun contenitore è fondamentale nei colloqui:
- Stack (list): LIFO, accesso da una sola estremità. Lo utilizzi per DFS, analisi delle espressioni e problemi con stack monotoni.
- Queue (deque con appendleft/popleft): FIFO, inserimento da un'estremità e rimozione dall'altra. La utilizzi per BFS e la pianificazione delle attività.
- Deque: entrambe le estremità sono accessibili in O(1). La utilizzi per finestre scorrevoli con scadenza (rimuovendo dal fronte) e con invariante monotono (rimuovendo dal fondo). Il massimo su una finestra scorrevole è il problema canonico delle deque.
La classe collections.deque di Python è lo strumento per tutti e tre i casi. Utilizzi append/pop per il comportamento di stack e append/popleft oppure appendleft/pop per il comportamento di coda o deque.
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]]}')Sottoarray più corto con somma almeno K: deque e somme prefisse
Shortest Subarray with Sum at Least K (LeetCode 862) è un problema avanzato che combina le somme prefisse con una deque monotona. Costruisca le somme prefisse, quindi utilizzi una deque per trovare, per ogni estremo destro, la somma prefissa più a sinistra che soddisfa prefix[right] - prefix[left] >= k. La deque mantiene somme prefisse crescenti (rimuova dal fondo per mantenere l'ordine crescente) ed estrae dal fronte per raccogliere le risposte valide.
È uno dei problemi più difficili sulle finestre scorrevoli perché coinvolge numeri negativi (che escludono il semplice approccio a due puntatori) e richiede che la deque svolga sia il ruolo di struttura monotona sia quello di meccanismo di scadenza.
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)) # 3Strategia per i colloqui sui problemi con deque
Identifichi un problema con deque monotona osservando questi segnali: (1) serve il massimo o il minimo di una finestra scorrevole di dimensione fissa, (2) serve una ricorrenza DP dp[i] = f(nums[i], max(dp[i-k..i-1])) oppure (3) serve l'indice valido più vicino che soddisfa una condizione monotona.
Durante i colloqui, scriva la soluzione con deque in modo ordinato: importi deque, mantenga i due invarianti (scadenza sul fronte e monotonicità sul fondo) e restituisca i risultati a partire dall'indice k-1. Menzioni sempre la complessità temporale O(n) e lo spazio O(k) per la deque (al massimo k indici memorizzati contemporaneamente), quindi la confronti con la forza bruta O(nk) per mostrare il miglioramento.
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))Verifica rapida
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: una deque decrescente monotona mantiene il massimo della finestra sul fronte, scartando dal fondo gli elementi più piccoli dei nuovi elementi, gli indici scaduti vengono rimossi dal fronte quando escono dai confini della finestra e ogni indice viene inserito ed estratto al massimo una volta, ottenendo O(n) complessivo con spazio O(k) per la deque. Ora risolveremo il problema dell'acqua piovana intrappolata utilizzando sia lo stack monotono sia l'approccio a due puntatori.
Domande Frequenti
La lezione «Massimo in una finestra scorrevole con deque monotona» è gratuita?
Sì — il testo completo di «Massimo in una finestra scorrevole con deque monotona» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Massimo in una finestra scorrevole con deque monotona»?
Mantenga una deque decrescente di indici per rispondere alle query del massimo nella finestra in O(1) per elemento, risolvendo il problema sliding-window-maximum in O(n). Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Massimo in una finestra scorrevole con deque monotona»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Stack monotono: crescente e decrescente
- Rettangolo più grande nell'istogramma
- Massimo in una finestra scorrevole con deque monotona
- Trapping Rain Water: stack e due puntatori