Calcolo di un movimento massimo

Question

Eventuali duplicati:
Find the min number in all contiguous subarrays of size l of a array of size n

Ho una (grande) array di dati numerici (dimensione N) e vorrebbe calcolare una matrice di esecuzione massimi con una dimensione fissa della finestra w.

Più direttamente, posso definire un nuovo array out[k-w+1] = max{data[k-w+1,...,k]} per k >= w-1 (ciò presuppone gli array basati su 0, come in C++).

C'è un modo migliore per farlo rispetto a N log(w)?

[Spero ci dovrebbe essere uno lineare in N senza dipendenza da w, come per lo spostamento medio, ma non riesce a trovarlo. Per N log(w) Penso che ci sia un modo per gestire con una struttura dati ordinata che farà insert(), delete() e extract_max() complessivamente in log(w) o meno su una struttura di dimensione w - come un albero binario ordinato, ad esempio].

Grazie mille.

Answer 1

Esiste effettivamente un algoritmo che può eseguire questa operazione in O (N) senza dipendere dalla dimensione della finestra w. L'idea è quella di utilizzare una struttura dati intelligente che supporta le seguenti operazioni:

• Enqueue, che aggiunge un nuovo elemento alla struttura,
• Dequeue, che rimuove l'elemento più antico dalla struttura, e
• Find-max, che restituisce (ma non rimuove) l'elemento minimo dalla struttura.

Questa è essenzialmente una struttura dati di coda che supporta l'accesso (ma non la rimozione) dell'elemento massimo. Sorprendentemente, come visto in this earlier question, è possibile implementare questa struttura dati in modo che ognuna di queste operazioni venga eseguita in tempo O (1) ammortizzato. Di conseguenza, se si utilizza questa struttura per accodare gli elementi w, quindi deselezionare e accodare continuamente un altro elemento nella struttura mentre si chiama find-max come necessario, ci vorrà solo il tempo O (n + Q), dove Q è il numero di domande che fai. Se ti interessa solo il minimo di ogni finestra una volta, questo diventa O (n), senza dipendere dalla dimensione della finestra.

Spero che questo aiuti!

Answer 2

ti spiegherò come farlo con l'elenco:

L = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6] 

con la lunghezza N=23 e W = 4.

fare due nuove copie del tuo elenco:

L1 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6] 
L2 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6] 

Loop da i=0 a N-1.Se i non è divisibile per W, quindi sostituire L1[i] con max(L1[i],L1[i-1]).

L1 = [21, 21, 21, 21, | 3, 9, 11, 18, | 19, 19, 19, 23 | 20, 20, 20, 20 | 1, 2, 22, 22 | 8, 12, 12] 

Loop da i=N-2 a 0. Se i+1 non è divisibile per W, quindi sostituire L2[i] con max(L2[i], L2[i+1]).

L2 = [21, 17, 16, 7 | 18, 18, 18, 18 | 23, 23, 23, 23 | 20, 15, 14, 14 | 22, 22, 22, 13 | 12, 12, 6] 

Fare una lista L3 di lunghezza N + 1 - W, in modo che L3[i] = max(L2[i], L1[i + W - 1])

L3 = [21, 17, 16, 11 | 18, 19, 19, 19 | 23, 23, 23, 23 | 20, 15, 14, 22 | 22, 22, 22, 13] 

Allora questa lista L3 è la massimi in movimento che si cercano, L2[i] è il massimo del range tra i e la prossima linea verticale, mentre l1[i + W - 1] è il massimo dell'intervallo tra la linea verticale e i + W - 1.