Maksimum w przesuwanym oknie za pomocą deque
Utrzymywanie ekstremów okna w O(n)
Maksimum w przesuwanym oknie za pomocą deque to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Maksimum w oknie przesuwnym
Dana jest tablica i rozmiar okna k. Należy znaleźć maksimum w każdym oknie przesuwającym się w prawo. Naiwne rozwiązanie działa w czasie O(n razy k).
Szybsze rozwiązanie
Za pomocą monotonicznego deque można znaleźć wynik dla każdego okna w łącznym czasie O(n), skanując tablicę tylko raz.
Ponownie przechowuj indeksy
W deque przechowuj indeksy, a nie wartości. Indeksy pozwalają sprawdzić, czy element z początku wysunął się poza bieżące okno.
from collections import deque
dq = deque()
res = []Utrzymuj kolejność malejącą
Wartości w deque są uporządkowane malejąco od początku do końca, więc indeks na początku zawsze wskazuje maksimum bieżącego okna.
Usuwaj mniejsze elementy z końca
Przed dodaniem indeksu i usuwaj elementy z końca, dopóki ich wartości są mniejsze, ponieważ nigdy nie mogą stać się maksimum w przyszłości.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Dodaj nowy indeks
Po usunięciu słabszych elementów z końca append bieżący indeks. Kolejność w deque pozostanie poprawna w kolejnych krokach.
dq.append(i)Usuń nieaktualny początek
Jeśli indeks na początku wypadł poza okno, wykonaj na nim popleft. Okno o rozmiarze k zaczyna się przy indeksie i minus k plus jeden.
if dq[0] <= i - k:
dq.popleft()Zapisuj każde maksimum
Gdy przy indeksie k minus jeden pojawi się pierwsze pełne okno, początek deque zawiera odpowiedź dla każdego kolejnego położenia.
if i >= k - 1:
res.append(nums[dq[0]])Pamiętaj o kolejności usuwania
Usuń nieaktualny początek przed odczytaniem odpowiedzi. W przeciwnym razie można zgłosić maksimum, które już opuściło okno.
Dlaczego czas pozostaje liniowy
Każdy indeks jest dodawany i usuwany najwyżej raz, więc praca deque zajmuje amortyzowane O(1) na krok i O(n) łącznie.
Minimum w oknie, ta sama idea
W przypadku minimum w oknie przesuwnym utrzymuj kolejność rosnącą w deque. Wystarczy odwrócić porównanie podczas usuwania elementów z końca.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Szybkie sprawdzenie
Co zawiera początek monotonicznego deque w problemie maksimum w oknie przesuwnym?
Podsumowanie: deque wygrywa z oknem
Utrzymywali Państwo malejący deque indeksów: usuwali Państwo małe elementy z końca, usuwali nieaktualny początek i odczytywali początek, aby znaleźć maksimum każdego okna w czasie O(n). 🏆
Często zadawane pytania
Czy lekcja „Maksimum w przesuwanym oknie za pomocą deque” jest bezpłatna?
Tak — pełny tekst „Maksimum w przesuwanym oknie za pomocą deque” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Maksimum w przesuwanym oknie za pomocą deque”?
Utrzymywanie ekstremów okna w O(n) Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Maksimum w przesuwanym oknie za pomocą deque”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Stosy do dopasowywania nawiasów
- Stos monotoniczny: następny większy element
- Kolejki i collections.deque
- Maksimum w przesuwanym oknie za pomocą deque