Valore minimo dei valori massimi nei sottosegmenti ... in O (n) complessità

Question

Ho intervistato alcuni giorni fa Amazon. Non ho potuto rispondere a una delle domande che mi hanno chiesto per la loro soddisfazione. Ho cercato di ottenere la risposta dopo l'intervista ma finora non ho avuto successo. Ecco la domanda:

Si dispone di un array di numeri interi di dimensione n. Viene fornito il parametro k dove k < n. Per ogni segmento di elementi consecutivi di dimensioni k nella matrice è necessario calcolare il valore massimo. Hai solo bisogno di restituire il valore minimo di questi valori massimi.

Ad esempio con 1 2 3 1 1 2 1 1 1 e k = 3 la risposta è 1.
I segmenti sarebbero 1 2 3, 2 3 1, 3 1 1, 1 1 2, 1 2 1, 2 1 1, 1 1 1.
I valori massimi di ciascun segmento sono 3, 3, 3, 2, 2, 2, 1.
Il minimo di questi valori è 1 quindi la risposta è 1.

La risposta migliore che ho trovato è di complessità O (n log k). Quello che faccio è creare un albero di ricerca binario con i primi elementi k, ottenere il valore massimo nell'albero e salvarlo nella variabile minOfMax, quindi eseguire il ciclo di un elemento alla volta con gli elementi rimanenti nell'array, rimuovere il primo elemento in il segmento precedente dall'albero di ricerca binario, inserire l'ultimo elemento del nuovo segmento nell'albero, ottenere l'elemento massimo nell'albero e confrontarlo con minOfMax lasciando in minOfMax il valore minimo dei due.

La risposta ideale deve essere di complessità O (n). Grazie.

Answer 1

Esiste un modo molto intelligente per eseguire ciò correlato a this earlier question. L'idea è che è possibile creare un queue data structure that supports enqueue, dequeue, and find-max in amortized O(1) time (ci sono molti modi per farlo, due sono spiegati nella domanda originale). Una volta che hai questa struttura dati, inizia aggiungendo i primi k elementi dalla matrice alla coda in tempo O (k). Poiché la coda supporta O (1) find-max, puoi trovare il massimo di questi elementi k in O (1). Quindi, deselezionare continuamente un elemento dalla coda e accodare (in O (1) volta) il successivo elemento dell'array. È quindi possibile interrogare in O (1) quale sia il massimo di ciascuno di questi sottoarray k-elemento. Se si tiene traccia del minimo di questi valori che si vedono nel corso dell'array, allora si ha un algoritmo O (n) -time, O (k) -space per trovare il massimo minimo dei subarray dell'elemento k.

Spero che questo aiuti!

Answer 2

La risposta di @ templatetypedef funziona, ma penso di avere un approccio più diretto.

Avviare calcolando il massimo per i seguenti intervalli (chiusi):

[k-1, k-1] 
[k-2, k-1] 
[k-3, k-1] 
... 
[0, k-1] 

Nota che ognuno di questi può essere calcolato in tempo costante da quella precedente.

Avanti, calcolare il massimo per questi intervalli:

[k, k] 
[k, k+1] 
[k, k+2] 
... 
[k, 2k-1] 

Ora questi intervalli:

[2k-1, 2k-1] 
[2k-2, 2k-1] 
[2k-3, 2k-1] 
... 
[k+1, 2k-1] 

Successiva Ti gli intervalli da 2k a 3K-1 ("inoltra intervalli"), poi da 3k-1 a 2k + 1 ("intervalli indietro"). E così via fino a raggiungere la fine dell'array.

Metti tutti questi in un grande tavolo. Si noti che ogni voce in questa tabella ha richiesto un tempo costante per il calcolo. Osservare che ci sono al massimo 2 * n intervalli nella tabella (perché ogni elemento appare una volta sul lato destro di un "intervallo in avanti" e una volta sul lato sinistro di un "intervallo indietro").

Ora, se [a, b] è un qualsiasi intervallo di ampiezza k, deve contenere esattamente uno 0, k, 2k, ...

dire che contiene m * k.

Osservare che gli intervalli [a, m * k-1] e [m * k, b] sono entrambi da qualche parte nella nostra tabella. Quindi possiamo semplicemente cercare il massimo per ciascuno, e il massimo di questi due valori è il massimo dell'intervallo [a, b].

Quindi per ogni intervallo di larghezza k, possiamo usare la nostra tabella per ottenere il massimo in tempo costante. Possiamo generare la tabella in tempo O (n). Il risultato segue.

Answer 3

Ecco l'implementazione (C#) della risposta di templatetypedef.

public static void printKMax(int[] arr, int n, int k) 
    { 
     Deque<int> qi = new Deque<int>(); 
     int i; 
     for (i=0;i< k; i++) // first window of the array 
     { 
      while ((qi.Count > 0) && (arr[i] >= arr[qi.PeekBack()])) 
      { 
       qi.PopBack(); 
      } 
      qi.PushBack(i); 
     } 

     for(i=k ;i< n; ++i) 
     { 
      Console.WriteLine(arr[qi.PeekFront()]); // the front item is the largest element in previous window. 
      while (qi.Count > 0 && qi.PeekFront() <= i - k) // this is where the comparison is happening! 
      { 
       qi.PopFront(); //now it's out of its window k 
      } 
      while(qi.Count>0 && arr[i]>=arr[qi.PeekBack()]) // repeat 
      { 
       qi.PopBack(); 
      } 
      qi.PushBack(i); 
     } 

     Console.WriteLine(arr[qi.PeekFront()]); 
    }