Sliding Window Maximum
Ti viene dato un array di interi nums e una dimensione della finestra k. Una finestra copre k valori consecutivi. Inizia all’estremità sinistra dell’array e si sposta di una posizione verso destra alla volta, finché il suo bordo destro non raggiunge l’ultimo valore.
Restituisci un array con il valore più grande all’interno della finestra in ciascuna delle sue posizioni, da sinistra a destra. Un array di lunghezza n ha n-k+1 finestre, quindi il risultato contiene n-k+1 valori.
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, da sinistra a destra.
Esempi
- Input
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- Output
- [12, 12, 12, 8, 8]
- Spiegazione
- 12 si trova nelle prime tre finestre,
[4, 2, 12],[2, 12, 3]e[12, 3, 8]. Dopo che scivola fuori, le finestre[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
- Gli intervalli sono
[-3, -1],[-1, -7]e[-7, -2]. Il maggiore tra due numeri negativi è quello più vicino allo zero, quindi si ottengono -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 massimo è 6 e la seconda occorrenza di 6 non aggiunge una seconda risposta.
+15 test nascosti all’invio
Per approfondire
Riesci a creare una coda che consenta di aggiungere un valore in fondo, rimuovere il valore in testa e leggere il suo massimo attuale, ciascuna operazione in tempo ammortizzato O(1)?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Esaminare ogni finestra per trovare il valore più grande richiede
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 precedente 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 precedente, ed è almeno altrettanto grande. Puoi eliminare definitivamente quei valori precedenti.
Mantieni gli indici dei valori che restano in una coda a doppia estremità, con i valori strettamente decrescenti dalla testa alla coda. Per ogni nuovo indice, rimuovi dalla coda gli indici dei valori più piccoli o uguali in fondo, aggiungi l'indice, rimuovi quello in testa se è uscito dalla finestra e leggi il massimo della finestra in testa.
Soluzione
Le finestre adiacenti condividono k-1 valori, quindi calcolare ogni massimo da zero ripete quasi tutto il lavoro. La parte difficile è che un massimo non può essere annullato: quando il valore più grande scorre fuori a sinistra, ti serve il successivo più grande senza rileggere la finestra. Una deque monotona mantiene, in ordine, esattamente i valori che potrebbero ancora diventare un massimo, così la risposta è sempre in testa e ogni indice entra ed esce una volta.
Scansiona ogni finestra
Corretto, ma non termina sui test più grandi
Intuizione
L’idea più diretta segue l’enunciato. La finestra che inizia all’indice start copre da start a start+k-1. Leggi quei k valori, tieni il più grande e sposta l’inizio di un passo verso destra. Ci sono n-k+1 posizioni iniziali, da 0 a n-k.
È corretto per definizione: ogni finestra viene letta per intero, quindi il suo valore massimo non può sfuggire. La memoria aggiuntiva consiste in una variabile per il massimo corrente, oltre al risultato.
È lento. Ognuna delle n-k+1 finestre richiede k letture e il prodotto è massimo quando k è circa la metà di n. Con n = 2 × 10^4 e k = 10^4 si tratta di 10^4 finestre di 10^4 valori, cioè 10^8 letture. Peggio ancora, due finestre vicine condividono k-1 valori, quindi quasi ogni lettura ripete un valore che avevi già letto.
Algoritmo
- Crea una lista dei risultati vuota.
- Fai scorrere
startda 0 an-k. - Imposta
bestsunums[start], poi confrontalo con ogni valore fino anums[start+k-1]e conserva quello più grande. - Aggiungi
bestai risultati. - Restituisci i risultati.
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: indici da 0 a k-1, poi da k a 2k-1 e così via, con un ultimo blocco più corto se n non è un multiplo di k. Una finestra è lunga esattamente k, quindi corrisponde a un blocco oppure copre la fine di un blocco e l’inizio del successivo. Non tocca mai tre blocchi.
Questo suggerisce di usare due array. fromStart[i] è il valore massimo dall’inizio del blocco di i fino a i, calcolato da sinistra a destra e azzerato all’inizio di ogni blocco. toEnd[i] è il valore massimo da i fino alla fine del suo blocco, calcolato da destra a sinistra e azzerato alla fine di ogni blocco. La finestra che inizia in i termina in i+k-1. La sua parte sinistra è coperta da toEnd[i] e quella destra da fromStart[i+k-1], quindi il suo massimo è il maggiore tra i due. Quando la finestra coincide con un intero blocco, entrambe le parti hanno il massimo di quel blocco e la risposta è comunque corretta.
Con nums = [4, 2, 12, 3, 8, 5, 1] e k = 3, i blocchi sono [4, 2, 12], [3, 8, 5] e [1]. fromStart è [4, 4, 12, 3, 8, 8, 1] e toEnd è [12, 12, 12, 8, 8, 5, 1]. La finestra [2, 12, 3] inizia in 1: toEnd[1] = 12 copre 2 e 12, fromStart[3] = 3 copre 3 e la risposta è 12.
Questo algoritmo ha una complessità temporale di O(n) e richiede tre passaggi sull’array. Il costo consiste nell’usare due array di supporto di lunghezza n; inoltre, serve l’intero array prima di poter calcolare il risultato per la prima finestra.
Algoritmo
- Riempi
fromStartda sinistra a destra: copianums[i]quandoiè un multiplo dik, altrimenti prendi il maggiore trafromStart[i-1]enums[i]. - Riempi
toEndda destra a sinistra: copianums[i]quandoiè l'ultimo indice oppurei+1è un multiplo dik, altrimenti prendi il maggiore tratoEnd[i+1]enums[i]. - Per ogni inizio
ida 0 an-k, aggiungi il maggiore tratoEnd[i]efromStart[i+k-1]. - Restituisci il risultato.
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
Parti da un'osservazione. Supponi che l'indice j preceda l'indice i e che nums[j] ≤ nums[i]. Ogni finestra successiva che contiene ancora j contiene anche i, perché i è più a destra e uscirà più tardi. In tutte quelle finestre nums[i] è almeno altrettanto grande, quindi j non potrà più essere il massimo. Quando arriva i, j è inutile e puoi dimenticartene.
Mantieni una coda a doppia estremità degli indici che non hai dimenticato. Quando arriva i, rimuovi dal fondo gli indici i cui valori sono minori o uguali a nums[i], poi aggiungi i. Gli indici rimasti hanno quindi valori strettamente decrescenti dalla testa alla coda, perché qualsiasi valore precedente che non fosse maggiore sarebbe stato rimosso. Perciò la testa contiene il valore più grande della finestra. La deque memorizza gli indici, non i valori, perché anche l'elemento in testa deve uscire quando la finestra lo supera: la finestra che termina a i inizia a i-k+1, quindi l'indice i-k è quello che è scivolato fuori e, se si trova in testa, lo rimuovi.
Segui nums = [4, 2, 12, 3, 8, 5, 1] con k = 3, elencando i valori nella deque. Entra 4: [4]. 2 è più piccolo, quindi resta dietro: [4, 2]. 12 rimuove entrambi: [12], e la risposta per la prima finestra è 12. 3 resta in attesa: [12, 3], risposta 12. 8 rimuove 3: [12, 8], risposta 12. 5 resta in attesa: [12, 8, 5], ma 12 si trova all'indice 2 e la finestra che termina all'indice 5 inizia all'indice 3, quindi 12 è scivolato fuori: [8, 5], risposta 8. 1 resta in attesa: [8, 5, 1], risposta 8.
Perché è O(n): il ciclo interno può rimuovere diversi indici in un singolo passaggio, ma ogni indice viene aggiunto una volta e rimosso al massimo una volta, dal fondo quando un valore maggiore lo supera o dalla testa quando scivola fuori. Tutte le rimozioni dell'intera esecuzione sommano al massimo a n, quindi il lavoro totale è al massimo di 2n operazioni sulla deque. Ogni indice nella deque si trova all'interno della finestra corrente, quindi non contiene mai più di k indici.
Algoritmo
- Crea una deque vuota per gli indici e una lista dei risultati vuota.
- Per ogni indice
i, rimuovi gli indici dalla fine finché la deque non è vuota e il valore in corrispondenza del suo ultimo indice è al massimonums[i]. - Aggiungi
ialla fine. - Se l'indice all'inizio è uguale a
i-k, è uscito dalla finestra: rimuovilo dall'inizio. - Quando
i ≥ k-1, una finestra completa termina ini: aggiungi al risultato il valore corrispondente all'indice all'inizio. - Restituisci il 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
La maggior parte dei bug deriva dai limiti della finestra o da ciò che memorizza la deque.
- Memorizzare i valori invece degli indici. In tal caso, elimini il primo elemento quando è uguale a
nums[i-k], e i duplicati causano problemi. Con[3, 1, 3]ek = 2, il secondo 3 rimuove il primo e poi viene rimosso a sua volta, perché è uguale al valore uscito dalla finestra. Memorizza gli indici e confronta il primo coni-k. - Fornire la risposta troppo presto o troppo tardi. La prima finestra completa termina all'indice
k-1, non ak, e il risultato deve contenere esattamenten-k+1valori. - Eliminare l'indice sbagliato. La finestra che termina a
iinizia ai-k+1, quindi l'indice che esce èi-k. Eliminarei-k+1rimuove un valore ancora presente nella finestra. - Leggere l'elemento in fondo o in testa a una deque vuota. Verifica che contenga qualcosa prima di confrontare con l'elemento in fondo.
- Considerare la deque una copia della finestra. Contiene solo i candidati, da 1 a
kindici, quindi la sua dimensione non ti dice nulla sulla finestra. - Nell'approccio a blocchi, dimenticare che l'ultimo blocco può essere più corto di
k. Anche la scansione da destra a sinistra deve ricominciare dall'ultimo indice, oltre che alla fine di ogni blocco.
Domande frequenti4
Qual è la complessità temporale del massimo in una finestra scorrevole?
La soluzione con deque monotona richiede tempo O(n). Ogni indice viene inserito una volta e rimosso al massimo una volta, quindi il ciclo interno esegue al massimo n rimozioni nell'intera esecuzione, anche se un singolo passaggio può rimuoverne diverse. La deque contiene al massimo k indici, quindi lo spazio aggiuntivo è O(k), oltre a quello occupato dal risultato.
Il problema del massimo della finestra scorrevole può essere risolto con un heap?
Sì. Inserisci le coppie di valore e indice in un max heap. Prima di leggere l'elemento in cima, estrailo finché il suo indice non è fuori dalla finestra, poiché le voci obsolete vengono rimosse solo quando raggiungono la cima. Questo richiede O(n log n) tempo e può contenere fino a n voci. La deque è più veloce e compatta perché rimuove i valori inutili non appena ne arriva uno più grande.
Perché la deque memorizza gli indici e non i valori?
Il fronte deve uscire quando la finestra lo supera, e solo il suo indice te lo indica. Con i soli valori dovresti fare un'ipotesi basandoti su nums[i-k], cosa che non funziona quando lo stesso valore compare più di una volta. L'indice ti fornisce anche il valore senza costi aggiuntivi, come nums[index].
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 una seconda uscita all'inizio per i valori troppo vecchi. Un problema senza scadenza, come trovare l'elemento successivo maggiore, richiede solo lo stack; una finestra scorrevole richiede entrambe le estremità. Inverti il confronto e lo stesso codice restituisce il minimo di ogni finestra.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def maxSlidingWindow(nums, k):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
Atteso
[12, 12, 12, 8, 8]