Sliding Window Maximum

TrudnePrzesuwane okno Stos monotoniczny Kolejka

+10

Otrzymujesz tablicę liczb całkowitych nums i rozmiar okna k. Okno obejmujące k kolejnych wartości zaczyna się na lewym końcu i przesuwa się w prawo o jedną pozycję naraz, aż jego prawa krawędź znajdzie się przy ostatniej wartości. Zwróć największą wartość w oknie na każdej pozycji, od lewej do prawej: n-k+1 wartości dla tablicy o długości n.

Funkcja

maxSlidingWindow(nums: integer-array, k: integer) → integer-array

numsinteger-array: tablica, po której przesuwa się okno
kinteger: liczba wartości w każdym oknie
Zwracainteger-array: największa wartość w każdym oknie, od najbardziej lewego do najbardziej prawego

Ograniczenia

1 ≤ k ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
The result contains nums.length-k+1 values, one for each window, ordered from left to right.

Przykłady

Wejście: nums = [4, 2, 12, 3, 8, 5, 1]k = 3
Wyjście: [12, 12, 12, 8, 8]
Wyjaśnienie: 12 znajduje się w pierwszych trzech oknach, więc każde z nich zwraca 12. Gdy wysuwa się z okna, zarówno [3, 8, 5], jak i [8, 5, 1] mają 8 jako największą wartość.

Wejście: nums = [-3, -1, -7, -2]k = 2
Wyjście: [-1, -1, -2]
Wyjaśnienie: Przedziały to [-3, -1], [-1, -7] i [-7, -2]. Większa z dwóch liczb ujemnych to ta bliższa zeru, co daje -1, -1 i -2.

Wejście: nums = [6, 6, 1]k = 3
Wyjście: [6]
Wyjaśnienie: Gdy k jest równe długości tablicy, istnieje jedno okno — cała tablica. Jej największa wartość to 6; druga kopia 6 nie daje drugiej odpowiedzi.

Pytanie dodatkowe

Czy potrafisz zbudować kolejkę, która umożliwia dodawanie wartości na końcu, usuwanie wartości z początku i odczytywanie jej bieżącej wartości maksymalnej, a każdą z tych operacji wykonuje w zamortyzowanym czasie O(1)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Sąsiednie okna współdzielą k-1 wartości, więc ponowne obliczanie każdego maksimum powtarza prawie całą pracę. Maksimum nie da się jednak cofnąć: gdy największa wartość wysunie się z okna, potrzebujesz kolejnej największej wartości, nie przeglądając okna ponownie. Monotoniczna kolejka dwustronna przechowuje tylko te wartości, które mogą jeszcze stać się maksimum, a odpowiedź znajduje się na jej początku.

Skanuj każde okno

Poprawne, ale nie kończy się na największych testach

Intuicja

Odczytaj wartości k z każdego okna i zachowaj największą. Każde okno jest odczytywane w całości, więc jego maksimum nie może zostać pominięte. Każde z n-k+1 okien wymaga k odczytów; najgorzej jest, gdy k wynosi mniej więcej połowę n: n = 2 × 10^4 i k = 10^4 dają około 10^4 okien po 10^4 wartości, czyli 10^8 odczytów.

Algorytm

Wykonuj pętlę dla start od 0 do n-k.
Wybierz największą wartość spośród nums[start] do nums[start+k-1].
Dodaj ją do wyniku i zwróć wynik po zakończeniu pętli.

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 result

Bloki z maksimami z każdej strony

Intuicja

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 k nie dzieli n. Okno ma dokładnie długość k, więc obejmuje cały blok albo koniec jednego bloku i początek następnego.

Oblicz więc wcześniej fromStart[i], czyli największą wartość od początku bloku i do i, oraz toEnd[i], czyli największą wartość od i do końca jego bloku. Okno zaczynające się w i kończy się na i+k-1: toEnd[i] obejmuje jego lewą część, a fromStart[i+k-1] prawą, więc większa z tych wartości jest maksimum okna. W pierwszym przykładzie okno [2, 12, 3] bierze toEnd[1] = 12 i fromStart[3] = 3, co daje 12.

Trzy przebiegi zapewniają czas O(n), kosztem dwóch tablic pomocniczych o długości n i konieczności posiadania całej tablicy przed uzyskaniem pierwszej odpowiedzi.

Algorytm

Wypełnij fromStart od lewej do prawej, zaczynając od nowa od nums[i], gdy i jest wielokrotnością k.
Wypełnij toEnd od prawej do lewej, zaczynając od nowa od nums[i] przy ostatnim indeksie i wszędzie tam, gdzie i+1 jest wielokrotnością k.
Dla każdego początku i od 0 do n-k dodaj większą z wartości toEnd[i] i fromStart[i+k-1].

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)]

Monotoniczna kolejka indeksów

Intuicja

Jeśli indeks j znajduje się przed i i nums[j] ≤ nums[i], to j nie może już nigdy być maksimum: każde późniejsze okno zawierające j zawiera również i, które opuszcza je później. Gdy więc pojawi się i, możesz zapomnieć o j.

Przechowuj w deque indeksy, których jeszcze nie zapomniano. Gdy pojawi się i, usuwaj z końca indeksy, których wartości są mniejsze lub równe nums[i], a następnie dodaj i. Pozostałe wartości ściśle maleją od początku do końca, więc pierwszy element jest maksimum w oknie. Przechowuj indeksy, ponieważ pierwszy element również musi zostać usunięty, gdy okno go minie. W pierwszym przykładzie, przy indeksie 5, deque zawiera 12, 8 i 5; 12 znajduje się pod indeksem 5 - 3 = 2, więc zostaje usunięte, a odpowiedzią jest 8.

Każdy indeks jest dodawany raz i usuwany najwyżej raz: najwyżej 2n operacji na deque, czas O(n). Deque nigdy nie zawiera więcej niż k indeksów.

Algorytm

Dla każdego indeksu i usuwaj indeksy z końca, dopóki kolejka dwustronna nie jest pusta, a wartość na jej końcu jest mniejsza lub równa nums[i].
Dodaj i na końcu.
Jeśli indeks na początku jest równy i-k, opuścił okno: usuń go.
Gdy i ≥ k-1, dodaj wartość z indeksu na początku do wyniku.

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

Pułapki i przypadki brzegowe

Przechowywanie wartości zamiast indeksów. Przy [3, 1, 3] i k = 2 druga 3 usuwa pierwszą z końca, a następnie sama zostaje usunięta, ponieważ jest równa nums[0], wartości, która opuściła okno.
Podawanie odpowiedzi za wcześnie lub za późno. Pierwsze pełne okno kończy się na indeksie k-1, a wynik musi zawierać dokładnie n-k+1 wartości.
Usuwanie elementu o indeksie i-k+1 zamiast i-k. Ten indeks nadal wskazuje pierwszą wartość w oknie.
Odczytywanie elementu z końca kolejki dwustronnej bez sprawdzenia, czy coś się w niej znajduje.
W podejściu blokowym zapominanie, że ostatni blok może być krótszy niż k. Przejście od prawej do lewej musi rozpoczynać się również od ostatniego indeksu, a także od końca każdego bloku.

Najczęstsze pytania3

C jaka jest złożoność czasowa problemu „Maksimum w przesuwanym oknie”?

Rozwiązanie z użyciem monotonicznej kolejki dwustronnej działa w czasie O(n), ponieważ każdy indeks jest dodawany raz i usuwany z kolejki co najwyżej raz. Kolejka przechowuje najwyżej k indeksów, więc dodatkowe zużycie pamięci wynosi O(k) oprócz miejsca zajmowanego przez wynik.

Czy problem maksimum w oknie przesuwnym można rozwiązać za pomocą kopca?

Tak. Wstawiaj pary wartości i indeksu do kopca maksymalnego, a przed odczytaniem elementu ze szczytu usuwaj go, jeśli jego indeks znajduje się poza oknem. Działa to w czasie O(n log n) i może przechowywać do n elementów. Kolejka dwustronna jest szybsza i zajmuje mniej miejsca, ponieważ odrzuca niepotrzebne wartości, gdy tylko pojawi się większa.

Jaka jest różnica między monotoniczną kolejką dwustronną a monotonicznym stosem?

Koniec kolejki dwustronnej działa jak stos monotoniczny: zanim dodasz wartość, usuwasz te, które przez nią stają się bezużyteczne. Kolejka dwustronna dodaje możliwość usuwania z przodu wartości, które są już zbyt stare. Następny większy element nie ma terminu ważności, więc potrzebuje tylko stosu. Odwróć porównanie, a kolejka dwustronna poda minimum w każdym oknie.

def maxSlidingWindow(nums, k):
    # Napisz tutaj kod

Test #1

Test #2

Test #3

Argumenty

nums = [4, 2, 12, 3, 8, 5, 1]
k = 3

Oczekiwany wynik

[12, 12, 12, 8, 8]

Sliding Window Maximum

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Skanuj każde okno

Bloki z maksimami z każdej strony

Monotoniczna kolejka indeksów

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania