Massimo di una finestra scorrevole con Deque
Mantenere gli estremi della finestra in O(n)
Massimo di una finestra scorrevole con Deque è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 4 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 Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Il massimo della finestra scorrevole
Dato un array e una dimensione della finestra k, vuole trovare il massimo di ogni finestra mentre scorre verso destra. Farlo in modo ingenuo richiede O(n per k).
Una promessa più veloce
Con un deque monotono può ottenere la risposta per ogni finestra in un tempo totale O(n), scorrendo l'array una sola volta.
Memorizzare di nuovo gli indici
Mantenga nel deque gli indici, non i valori. Gli indici consentono di verificare se l'elemento in testa è uscito dalla finestra corrente.
from collections import deque
dq = deque()
res = []Mantenerlo decrescente
Il deque resta decrescente per valore, dalla testa alla coda, quindi l'indice in testa punta sempre al massimo della finestra.
Eliminare le code più piccole
Prima di aggiungere l'indice i, esegua pop dalla coda finché i valori corrispondenti sono più piccoli, perché non potranno mai essere il massimo futuro.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Aggiungere il nuovo indice
Dopo aver eliminato gli elementi più deboli dalla coda, aggiunga l'indice corrente. L'ordine del deque resta corretto per i passaggi successivi.
dq.append(i)Espellere l'elemento obsoleto in testa
Se l'indice in testa è fuori dalla finestra, lo rimuova con popleft. Una finestra di dimensione k inizia all'indice i meno k più uno.
if dq[0] <= i - k:
dq.popleft()Registrare ogni massimo
Quando la prima finestra completa si forma all'indice k meno uno, la testa del deque contiene la risposta per ogni posizione successiva.
if i >= k - 1:
res.append(nums[dq[0]])Attenzione all'ordine di espulsione
Espella l'elemento obsoleto in testa prima di leggere la risposta. Altrimenti potrebbe riportare un massimo che ha già lasciato la finestra.
Perché il tempo lineare è garantito
Ogni indice viene aggiunto e rimosso al massimo una volta, quindi il lavoro sul deque è ammortizzato O(1) per passaggio e O(n) complessivamente.
Finestra minima, stessa idea
Per il minimo di una finestra scorrevole, mantenga invece il deque in ordine crescente. Basta invertire il confronto quando si elimina dalla coda.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Verifica rapida
Nel problema del massimo della finestra scorrevole, che cosa contiene la testa del deque monotono?
Riepilogo: il deque vince sulle finestre
Ha mantenuto un deque decrescente di indici: ha eliminato le code piccole, espulso la testa obsoleta e letto la testa per ottenere il massimo di ogni finestra in O(n). 🏆
Domande Frequenti
La lezione «Massimo di una finestra scorrevole con Deque» è gratuita?
Sì — il testo completo di «Massimo di una finestra scorrevole con Deque» è 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 Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Massimo di una finestra scorrevole con Deque»?
Mantenere gli estremi della finestra in O(n) Eserciti Competitive Programming Academy 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 Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Massimo di una finestra scorrevole con Deque»?
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 Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy 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 per le parentesi corrispondenti
- Stack monotono: elemento successivo maggiore
- Code e collections.deque
- Massimo di una finestra scorrevole con Deque