Sliding Window Maximum
Ti viene fornito un array di numeri interi nums e una dimensione della finestra k. Una finestra di k valori consecutivi inizia dall’estremità sinistra e si sposta verso destra di una posizione alla volta, finché il suo bordo destro non raggiunge l’ultimo valore. Restituisci il valore più grande nella finestra in ogni posizione, da sinistra a destra: n-k+1 valori per un array di lunghezza n.
Funzione
- numsinteger-array
- l’array su cui scorre la finestra
- kinteger
- il numero di valori in ogni finestra
- Restituisceinteger-array
- il valore più grande di ogni finestra, dalla finestra più a sinistra a quella più a destra
Vincoli
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- Il risultato contiene
nums.length-k+1valori, uno per finestra, in ordine da sinistra a destra.
Esempi
- Input
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- Output
- [12, 12, 12, 8, 8]
- Spiegazione
- 12 è all'interno delle prime tre finestre, quindi ognuna di esse restituisce 12. Dopo che scivola fuori,
[3, 8, 5]e[8, 5, 1]hanno entrambe 8 come valore massimo.
- Input
- nums = [-3, -1, -7, -2]k = 2
- Output
- [-1, -1, -2]
- Spiegazione
- Le finestre sono
[-3, -1],[-1, -7]e[-7, -2]. Il più grande tra due numeri negativi è quello più vicino allo zero, quindi otteniamo -1, -1 e -2.
- Input
- nums = [6, 6, 1]k = 3
- Output
- [6]
- Spiegazione
- Quando
kè uguale alla lunghezza dell’array, c’è una sola finestra: l’intero array. Il suo valore più grande è 6; la seconda occorrenza di 6 non aggiunge una seconda risposta.
Per approfondire
Riesci a costruire una coda che supporti l’aggiunta di un valore in fondo, la rimozione del valore in testa e la lettura del suo massimo attuale, ciascuna in tempo ammortizzato O(1)?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Esaminare ogni finestra per trovare il suo valore più grande costa
kpassaggi per finestra. Confronta due finestre adiacenti: condividonok-1valori, perché un valore esce a sinistra e uno entra a destra.Quando entra un nuovo valore, ogni valore più vecchio nella finestra che è minore o uguale a esso non potrà mai più essere un massimo. Il nuovo valore rimane in ogni finestra successiva che contiene ancora quello più vecchio, ed è almeno altrettanto grande. Puoi eliminare definitivamente quei valori più vecchi.
Mantieni gli indici dei valori che rimangono in una coda a doppia estremità, con i valori strettamente decrescenti dalla testa alla coda. Per ogni nuovo indice, rimuovi dalla coda gli elementi in fondo con valori minori o uguali, aggiungi l'indice, rimuovi il primo elemento se è uscito dalla finestra e leggi il massimo della finestra in testa.
Soluzione
Le finestre adiacenti condividono k-1 valori, quindi ricalcolare ogni massimo ripete quasi tutto il lavoro. Ma un massimo non può essere annullato: quando il valore più grande esce dalla finestra, hai bisogno del successivo più grande senza rileggere la finestra. Una deque monotona mantiene solo i valori che potrebbero ancora diventare un massimo, con la risposta in testa.
Scansiona ogni finestra
Corretto, ma non termina sui test più grandi
Intuizione
Leggi i valori k di ogni finestra e conserva il più grande. Ogni finestra viene letta per intero, quindi il suo massimo non può sfuggire. Ognuna delle n-k+1 finestre richiede k letture; il caso peggiore si verifica quando k è circa la metà di n: n = 2 × 10^4 e k = 10^4 danno circa 10^4 finestre di 10^4 valori, ovvero 10^8 letture.
Algoritmo
- Esegui un ciclo con
startda 0 an-k. - Prendi il valore più grande da
nums[start]anums[start+k-1]. - Aggiungilo al risultato e restituisci il risultato dopo il ciclo.
def maxSlidingWindow(nums, k):
result = []
for start in range(len(nums) - k + 1):
# Read all k values of this window again
result.append(max(nums[i] for i in range(start, start + k)))
return resultBlocchi con massimi da ciascun lato
Intuizione
Dividi l’array in blocchi di k: dagli indici 0 a k-1, poi da k a 2k-1 e così via, con un ultimo blocco più corto se k non divide n. Una finestra è lunga esattamente k, quindi corrisponde a un intero blocco oppure alla fine di un blocco seguita dall’inizio del successivo.
Precalcola quindi fromStart[i], il valore più grande dall’inizio del blocco di i fino a i, e toEnd[i], il valore più grande da i fino alla fine del suo blocco. La finestra che inizia in i termina in i+k-1: toEnd[i] copre la parte sinistra e fromStart[i+k-1] quella destra, quindi il maggiore dei due è il massimo della finestra. Nel primo esempio, la finestra [2, 12, 3] usa toEnd[1] = 12 e fromStart[3] = 3, ottenendo 12.
Tre passaggi richiedono un tempo O(n), al costo di due array di supporto di lunghezza n e della necessità di avere l’intero array prima di ottenere la prima risposta.
Algoritmo
- Riempi
fromStartda sinistra a destra, ricominciando connums[i]quandoiè un multiplo dik. - Riempi
toEndda destra a sinistra, ricominciando connums[i]all'ultimo indice e ogni volta chei+1è un multiplo dik. - Per ogni inizio
ida 0 an-k, aggiungi il maggiore tratoEnd[i]efromStart[i+k-1].
def maxSlidingWindow(nums, k):
n = len(nums)
# Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
from_start = [0] * n # max from the start of i's block up to i
to_end = [0] * n # max from i up to the end of i's block
for i in range(n):
if i % k == 0:
from_start[i] = nums[i]
else:
from_start[i] = max(from_start[i - 1], nums[i])
for i in range(n - 1, -1, -1):
if i == n - 1 or (i + 1) % k == 0:
to_end[i] = nums[i]
else:
to_end[i] = max(to_end[i + 1], nums[i])
# A window [i, i+k-1] is the tail of one block plus the head of the next.
return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]Deque monotona di indici
Intuizione
Se l'indice j viene prima di i e nums[j] ≤ nums[i], allora j non potrà mai più essere un massimo: ogni finestra successiva che contiene j contiene anche i, che esce più tardi. Quindi, quando arriva i, puoi dimenticare j.
Conserva una deque degli indici non ancora dimenticati. Quando arriva i, rimuovi gli indici dalla fine finché i loro valori sono minori o uguali a nums[i], poi aggiungi i. I valori rimasti diminuiscono strettamente da davanti a dietro, quindi il primo è il massimo della finestra. Memorizza gli indici, perché anche il primo deve essere rimosso quando la finestra lo supera. Nel primo esempio, all'indice 5 la deque contiene 12, 8 e 5; 12 si trova all'indice 5 - 3 = 2, quindi esce e la risposta è 8.
Ogni indice viene aggiunto una volta e rimosso al massimo una volta: al massimo 2n operazioni sulla deque, tempo O(n). La deque non contiene mai più di k indici.
Algoritmo
- Per ogni indice
i, rimuovi gli indici dalla parte posteriore finché la deque non è vuota e il valore in fondo è minore o uguale anums[i]. - Aggiungi
iin fondo. - Se l'indice in testa è uguale a
i-k, è uscito dalla finestra: rimuovilo. - Quando
i ≥ k-1, aggiungi il valore dell'indice in testa al risultato.
from collections import deque
def maxSlidingWindow(nums, k):
window = deque() # indices; their values strictly decrease from front to back
result = []
for i, x in enumerate(nums):
# A value at the back that is not bigger than x can never be a maximum again.
while window and nums[window[-1]] <= x:
window.pop()
window.append(i)
# The front index has slid out of the window on the left.
if window[0] == i - k:
window.popleft()
# From index k-1 on, every step completes a window; its maximum sits at the front.
if i >= k - 1:
result.append(nums[window[0]])
return result
Trappole e casi limite
- Memorizzare i valori invece degli indici. Con
[3, 1, 3]ek = 2, il secondo 3 rimuove il primo, poi viene rimosso a sua volta perché è uguale anums[0], il valore che è uscito. - Fornire la risposta troppo presto o troppo tardi. La prima finestra completa termina all'indice
k-1e il risultato deve contenere esattamenten-k+1valori. - Rimuovere l'indice
i-k+1invece dii-k. Quell'indice è ancora il primo valore della finestra. - Leggere l'ultimo elemento della deque senza verificare che contenga qualcosa.
- Nell'approccio a blocchi, dimenticare che l'ultimo blocco può essere più corto di
k. La scansione da destra a sinistra deve ripartire anche dall'ultimo indice, oltre che alla fine di ogni blocco.
Domande frequenti3
Qual è la complessità temporale del massimo nella finestra scorrevole?
La soluzione con una deque monotona ha una complessità temporale di O(n), perché ogni indice viene inserito una volta e rimosso al massimo una volta. La deque contiene al massimo k indici, quindi lo spazio aggiuntivo è O(k), oltre a quello del risultato.
È possibile risolvere Sliding Window Maximum con un heap?
Sì. Inserisci le coppie di valore e indice in un heap massimo e, prima di leggere l'elemento in cima, rimuovilo finché il suo indice è fuori dalla finestra. Richiede un tempo di O(n log n) e può contenere fino a n elementi. La deque è più veloce e occupa meno spazio perché elimina i valori inutili non appena ne arriva uno più grande.
Qual è la differenza tra una deque monotona e uno stack monotono?
Il retro della deque funziona come uno stack monotono: prima di inserire un valore, rimuovi quelli che rende inutili. La deque aggiunge un’uscita anteriore per i valori troppo vecchi. Il prossimo elemento maggiore non ha scadenza, quindi gli basta lo stack. Inverti il confronto e la deque fornisce il minimo di ogni finestra.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def maxSlidingWindow(nums, k):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
Output atteso
[12, 12, 12, 8, 8]