Sliding Window Maximum

Najbardziej bezpośredni pomysł wynika z treści zadania. Okno zaczynające się pod indeksem start obejmuje elementy od start do start+k-1. Odczytaj te k wartości, zachowaj największą i przesuń początek o jeden krok w prawo. Istnieje n-k+1 możliwych początków, od 0 do n-k.

To rozwiązanie jest poprawne z definicji: każde okno jest odczytywane w całości, więc jego największa wartość nie może zostać pominięta. Dodatkowa pamięć to jedna zmienna przechowująca bieżące maksimum, poza wynikiem.

To rozwiązanie jest powolne. Odczytanie każdego z n-k+1 okien wymaga k odczytów, a ich iloczyn jest największy, gdy k wynosi mniej więcej połowę n. Dla n = 2 × 10^4 i k = 10^4 oznacza to 10^4 okien po 10^4 wartości, czyli 10^8 odczytów. Co gorsza, dwa sąsiednie okna współdzielą k-1 wartości, więc niemal każdy odczyt powtarza jeden z tych, które już wykonano.

Podziel tablicę na bloki o długości k: indeksy od 0 do k-1, następnie od k do 2k-1 i tak dalej; ostatni blok będzie krótszy, jeśli n nie jest wielokrotnością k. Okno ma dokładnie k elementów, więc albo pokrywa się z jednym blokiem, albo obejmuje koniec jednego bloku i początek następnego. Nigdy nie obejmuje trzech bloków.

To sugeruje użycie dwóch tablic. fromStart[i] to największa wartość od początku bloku zawierającego i do i; tablicę tę wypełnia się od lewej do prawej i resetuje na początku każdego bloku. toEnd[i] to największa wartość od i do końca jego bloku; tablicę tę wypełnia się od prawej do lewej i resetuje na końcu każdego bloku. Okno zaczynające się na i kończy się na i+k-1. Jego lewą część obejmuje toEnd[i], a prawą fromStart[i+k-1], więc maksimum okna to większa z tych dwóch wartości. Gdy okno obejmuje cały blok, obie części mają maksimum tego bloku, więc wynik nadal jest poprawny.

Dla nums = [4, 2, 12, 3, 8, 5, 1] i k = 3 bloki to [4, 2, 12], [3, 8, 5] i [1]. fromStart wynosi [4, 4, 12, 3, 8, 8, 1], a toEnd wynosi [12, 12, 12, 8, 8, 5, 1]. Okno [2, 12, 3] zaczyna się na indeksie 1: toEnd[1] = 12 obejmuje 2 i 12, fromStart[3] = 3 obejmuje 3, a wynikiem jest 12.

Algorytm działa w czasie O(n) i wymaga trzech przejść przez tablicę. Kosztem są dwie pomocnicze tablice o długości n; ponadto przed obliczeniem wyniku dla pierwszego okna potrzebna jest cała tablica.

Zacznij od jednej obserwacji. Załóżmy, że indeks j występuje przed indeksem i i nums[j] ≤ nums[i]. Każde późniejsze okno, w którym nadal znajduje się j, zawiera też i, ponieważ i leży dalej na prawo i opuszcza okno później. We wszystkich tych oknach nums[i] jest co najmniej tak duże, więc j nie może już być maksimum. Gdy pojawia się i, j staje się nieprzydatne i możesz o nim zapomnieć.

Przechowuj w kolejce dwustronnej indeksy, o których jeszcze nie zapomniano. Gdy pojawia się i, usuwaj indeksy z końca kolejki, dopóki ich wartości są nie większe niż nums[i], a następnie dodaj i. Pozostałe wartości będą wtedy ściśle malejące od początku do końca, ponieważ każda starsza wartość, która nie była większa, zostałaby usunięta. Zatem na początku kolejki znajduje się największa wartość w oknie. Deque przechowuje indeksy, a nie wartości, ponieważ indeks z początku kolejki również musi zostać usunięty, gdy okno go minie: okno kończące się na i zaczyna się na i-k+1, więc indeks i-k to ten, który właśnie wypadł z okna; jeśli znajduje się na początku kolejki, usuń go.

Prześledź nums = [4, 2, 12, 3, 8, 5, 1] dla k = 3, wypisując wartości w kolejce dwustronnej. Pojawia się 4: [4]. 2 jest mniejsze, więc czeka za nim: [4, 2]. 12 usuwa obie wartości: [12], a odpowiedzią dla pierwszego okna jest 12. 3 czeka: [12, 3], odpowiedź 12. 8 usuwa 3: [12, 8], odpowiedź 12. 5 czeka: [12, 8, 5], ale 12 znajduje się na indeksie 2, a okno kończące się na indeksie 5 zaczyna się na indeksie 3, więc 12 wypadło z okna: [8, 5], odpowiedź 8. 1 czeka: [8, 5, 1], odpowiedź 8.

Dlaczego złożoność wynosi O(n): pętla wewnętrzna może usunąć kilka indeksów w jednym kroku, ale każdy indeks jest dodawany raz i usuwany najwyżej raz — z końca, gdy pokona go większa wartość, albo z początku, gdy wypadnie z okna. Łączna liczba usunięć w całym przebiegu wynosi najwyżej n, więc łączna praca to najwyżej 2n operacji na kolejce dwustronnej. Każdy indeks w kolejce należy do bieżącego okna, więc kolejka nigdy nie zawiera ich więcej niż k.