Minimalna wartość maksymalnych wartości w podsegmentach ... w złożoności O (n)

Question

Przeprowadziłem wywiad z Amazon kilka dni temu. Nie mogłem odpowiedzieć na jedno z pytań, które zadał mi do zadowolenia. Próbowałem uzyskać odpowiedź po wywiadzie, ale jak dotąd nie udało mi się. Oto pytanie:

Masz tablicę liczb całkowitych o wielkości n. Dostaniesz parametr k gdzie k < n. Dla każdego segmentu kolejnych elementów o rozmiarze k w tablicy należy obliczyć wartość maksymalną. Musisz tylko zwrócić minimalną wartość tych maksymalnych wartości.

Na przykład podając 1 2 3 1 1 2 1 1 1 i k = 3 odpowiedź brzmi: 1.
Segmenty byłoby 1 2 3, 2 3 1, 3 1 1, 1 1 2, 1 2 1, 2 1 1, 1 1 1.
Maksymalne wartości w każdym segmencie są 3, 3, 3, 2, 2, 2, 1.
Minimalna z tych wartości to 1, więc odpowiedź brzmi: 1.

Najlepsza odpowiedź, jaką wymyśliłem, to złożoność O (n log k). Co mogę zrobić, to utworzyć binarne drzewo wyszukiwania z pierwszymi elementami k, uzyskać maksymalną wartość w drzewie i zapisać je w zmiennej minOfMax, a następnie zapętlić po jednym elemencie z pozostałymi elementami w tablicy, usunąć pierwszy element poprzedni segment z drzewa wyszukiwania binarnego, wstaw ostatni element nowego segmentu w drzewie, uzyskaj maksymalny element w drzewie i porównaj go z minOfMax, pozostawiając w minOfMax minimalną wartość dwóch.

Idealna odpowiedź musi być złożona O (n). Dziękuję.

Answer 1

Istnieje bardzo sprytny sposób na zrobienie tego, co jest związane z this earlier question. Chodzi o to, że możliwe jest zbudowanie queue data structure that supports enqueue, dequeue, and find-max in amortized O(1) time (jest na to wiele sposobów, dwa są wyjaśnione w oryginalnym pytaniu). Po uzyskaniu tej struktury danych zacznij od dodania pierwszych k elementów z tablicy do kolejki w czasie O (k). Ponieważ kolejka obsługuje O-1 find-max, możesz znaleźć maksimum tych elementów w czasie O (1). Następnie, ciągle usuwaj element z kolejki i zapisuj (w czasie O (1) następny element tablicy. Następnie możesz zapytać w O (1), jaka jest maksymalna wartość każdej z tych pod-tablic k-element. Jeśli śledzisz minimum tych wartości, które widzisz w ciągu tablicy, masz algorytm O (n) -time, O (k) -space do znalezienia minimalnego maksimum subarrayów elementu k.

Mam nadzieję, że to pomoże!

Answer 2

Odpowiedź @ templatetypedef działa, ale myślę, że mam bardziej bezpośrednie podejście.

Rozpoczęcie przez obliczenie maksymalnej w następujących odstępach czasu (zamknięte):

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

Należy zauważyć, że każdy z nich może być obliczona w stałym czasie od poprzedzającego jeden.

Następnie obliczyć max dla tych przedziałów:

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

Teraz te przedziały:

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

Następny robisz odstępy od 2k do 3k-1 ("przekazuje interwały"), a następnie od 3k-1 do 2k + 1 ("odstępy wstecz"). I tak dalej, aż dojdziesz do końca tablicy.

Umieść wszystkie te elementy w dużym stole. Należy zauważyć, że każdy wpis w tej tabeli wymagał stałego obliczenia. Zauważ, że w tabeli są co najwyżej 2 * n przedziały (ponieważ każdy element pojawia się raz po prawej stronie "interwału do przodu" i raz po lewej stronie "odstępu wstecznego").

Teraz, jeśli [a, b] jest dowolny przedział o szerokości k, musi zawierać dokładnie jeden z 0, k, 2k, ...

powiedzieć, że zawiera m * K.

Zauważ, że przedziały [a, m * k-1] i [m * k, b] znajdują się gdzieś w naszym stole. Możemy więc po prostu wyszukać maksimum dla każdego, a maksimum tych dwóch wartości jest maksimum przedziału [a, b].

Tak więc dla każdego przedziału szerokości k możemy użyć naszej tabeli, aby uzyskać jej maksymalną wartość w stałym czasie. Możemy wygenerować tabelę w czasie O (n). Wynik następuje.

Answer 3

Oto implementacja (C#) odpowiedzi 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()]); 
    }