Maksimum w oknie przesuwnym za pomocą monotonicznej kolejki dwustronnej
Utrzymywać malejącą kolejkę dwustronną indeksów, aby odpowiadać na zapytania o maksimum w oknie w czasie O(1) na element i rozwiązać problem sliding-window-maximum w czasie O(n)
Maksimum w oknie przesuwnym za pomocą monotonicznej kolejki dwustronnej to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 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.
Problem maksimum w przesuwającym się oknie
Problem maksimum w przesuwającym się oknie (LeetCode 239) polega na otrzymaniu tablicy i rozmiaru okna k. Gdy okno przesuwa się z lewej do prawej strony, za każdym razem o jedną pozycję, należy wypisać największy element w każdym oknie. Podejście siłowe oblicza maksimum każdego okna zawierającego k elementów w czasie O(k), co daje łącznie O(nk) i jest zbyt wolne dla dużych wartości k.
Rozwiązanie z użyciem monotonicznej kolejki dwustronnej (deque) osiąga łączną złożoność O(n), utrzymując malejącą kolejkę indeksów. Na początku kolejki zawsze znajduje się indeks maksimum bieżącego okna, co zapewnia zapytania o maksimum w czasie O(1), a jednocześnie umożliwia operacje na początku i na końcu kolejki.
from collections import deque
# Brute force O(nk) for comparison
def sliding_max_brute(nums, k):
return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print('Input:', nums, 'k=', k)
print('Expected: [3, 3, 5, 5, 6, 7]')
print('Brute: ', sliding_max_brute(nums, k))Monotoniczna kolejka dwustronna: najważniejsza idea
Należy utrzymywać monotoniczną kolejkę dwustronną malejącą, która przechowuje indeksy, a nie wartości. Niezmiennik ma postać: nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[-1]]. Przed dodaniem indeksu i:
- Usunąć wygasłe indeksy z początku: jeśli
deque[0] <= i - k, indeks wypadł już z okna. - Usunąć indeksy o mniejszych wartościach z końca: dopóki
nums[deque[-1]] <= nums[i], tych indeksów nie można już użyć jako maksimum żadnego przyszłego okna (znajdują się bardziej na lewo i mają mniejsze wartości), więc należy je odrzucić.
Po wykonaniu tych operacji należy dodać i na końcu kolejki. Na jej początku zawsze znajduje się maksimum bieżącego okna.
from collections import deque
def sliding_window_max(nums, k):
dq = deque() # stores indices; values are decreasing
result = []
for i, n in enumerate(nums):
# 1. Remove indices outside the current window
while dq and dq[0] <= i - k:
dq.popleft()
# 2. Remove indices with smaller values from the back
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
# 3. Record max when first full window is complete
if i >= k - 1:
result.append(nums[dq[0]]) # front = max of current window
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3)) # [3, 3, 5, 5, 6, 7]Prześledzenie działania kolejki dwustronnej krok po kroku
Prześledźmy działanie dla [1, 3, -1, -3, 5, 3, 6, 7] przy k=3:
- i=0 (1): dq=[0]
- i=1 (3): pop 0 (1<3), dq=[1]
- i=2 (-1): -1<3, więc zachowujemy element, dq=[1,2]. Okno [1,3,-1], maksimum=nums[1]=3
- i=3 (-3): -3<-1, dq=[1,2,3]. Sprawdzamy początek: 1 > 3-3=0, OK. Maksimum okna=3
- i=4 (5): pop 3,2,1 (wszystkie są mniejsze), dq=[4]. Początek 4 > 4-3=1, OK. Maksimum=5
- i=5 (3): 3<5, dq=[4,5]. Początek 4 > 5-3=2, OK. Maksimum=5
- i=6 (6): pop 5,4 (oba są mniejsze), dq=[6]. Maksimum=6
- i=7 (7): pop 6, dq=[7]. Maksimum=7
from collections import deque
def sliding_window_max_trace(nums, k):
dq = deque()
result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
print(f' Remove expired index {dq[0]} from front')
dq.popleft()
while dq and nums[dq[-1]] <= n:
print(f' Remove smaller index {dq[-1]} (val={nums[dq[-1]]}) from back')
dq.pop()
dq.append(i)
print(f'i={i} n={n}: dq={list(dq)} vals={[nums[j] for j in dq]}')
if i >= k - 1:
win_max = nums[dq[0]]
result.append(win_max)
print(f' Window {nums[max(0,i-k+1):i+1]} -> max={win_max}')
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
result = sliding_window_max_trace(nums, 3)
print('Result:', result)Dlaczego każdy element jest dodawany i usuwany najwyżej raz
Gwarancja złożoności O(n) wynika z tego samego argumentu amortyzacyjnego co w przypadku monotonicznego stosu: każdy indeks jest dodawany do kolejki dwustronnej dokładnie raz i usuwany najwyżej raz — z początku po wygaśnięciu albo z końca po zastąpieniu go przez lepszy element. Łączna liczba operacji na kolejce w całej pętli wynosi najwyżej 2n.
Wewnętrzne pętle while nie zwiększają ogólnej złożoności — każde usunięcie wykonane w tych pętlach jest „opłacone” przez wcześniejsze dodanie elementu. To takie samo rozumowanie jak w przypadku monotonicznego stosu, rozszerzone jednak na kolejkę dwustronną, która pozwala usuwać elementy z obu końców.
from collections import deque
def sliding_window_max_instrumented(nums, k):
dq = deque()
result = []
front_pops = back_pops = pushes = 0
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft(); front_pops += 1
while dq and nums[dq[-1]] <= n:
dq.pop(); back_pops += 1
dq.append(i); pushes += 1
if i >= k - 1:
result.append(nums[dq[0]])
print(f'n={len(nums)}: pushes={pushes}, front_pops={front_pops}, back_pops={back_pops}')
print(f'Total deque ops = {pushes + front_pops + back_pops} <= 3n = {3*len(nums)}')
return result
import random; random.seed(0)
nums = [random.randint(-100, 100) for _ in range(20)]
sliding_window_max_instrumented(nums, 5)Minimum w przesuwającym się oknie
Minimum w przesuwającym się oknie jest jego symetrycznym odpowiednikiem: należy utrzymywać monotoniczną kolejkę dwustronną rosnącą (usuwać elementy z końca, gdy nowy element jest mniejszy od elementu na końcu). Na początku kolejki zawsze znajduje się minimum bieżącego okna. Wszystkie pozostałe kroki są identyczne jak w wersji dla maksimum — należy jedynie odwrócić kierunek porównań.
Problemy dotyczące minimum w przesuwającym się oknie często pojawiają się jako podproblemy w większych algorytmach. Na przykład znalezienie minimalnego kosztu transportu towarów wzdłuż ścieżki z k przystankami pośrednimi może wymagać obliczania minimum w przesuwającym się oknie dla tablic DP.
from collections import deque
def sliding_window_min(nums, k):
dq = deque() # increasing monotonic deque
result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft() # expired
while dq and nums[dq[-1]] >= n:
dq.pop() # pop larger values from back
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]]) # front = min
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print('Max k=3:', sliding_window_min.__name__, '->', end=' ')
print(sliding_window_min(nums, 3)) # [-1, -3, -3, -3, 3, 3]
from collections import deque
def sliding_window_max(nums, k):
dq = deque(); result = []
for i, n in enumerate(nums):
while dq and dq[0] <= i-k: dq.popleft()
while dq and nums[dq[-1]] <= n: dq.pop()
dq.append(i)
if i >= k-1: result.append(nums[dq[0]])
return result
print('Max k=3:', sliding_window_max(nums, 3)) # [3,3,5,5,6,7]Gra w skoki VI: programowanie dynamiczne z monotoniczną kolejką dwustronną
Gra w skoki VI (LeetCode 1696) to klasyczny przykład połączenia programowania dynamicznego z monotoniczną kolejką dwustronną. Mając tablicę i maksymalny rozmiar skoku k, zaczynamy od indeksu 0. W każdym kroku można przeskoczyć od 1 do k pozycji naprzód, dodając wynik z docelowego pola. Należy zmaksymalizować łączny wynik. Rekurencja DP ma postać dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]). Obliczanie maksimum w przesuwającym się oknie dla tablicy DP daje łączną złożoność O(n).
Ten schemat — rekurencja DP, w której każda komórka zależy od maksimum ze stałej długości okna wcześniejszych komórek — pojawia się często i zawsze wskazuje na użycie monotonicznej kolejki dwustronnej.
from collections import deque
def max_result(nums, k):
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
dq = deque([0]) # indices of max dp values in current window
for i in range(1, n):
# Remove expired indices
while dq and dq[0] < i - k:
dq.popleft()
# dp[i] = nums[i] + max dp in window [i-k, i-1]
dp[i] = nums[i] + dp[dq[0]]
# Maintain decreasing deque on dp values
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
return dp[n - 1]
print(max_result([1,-1,-2,4,-7,3], 2)) # 7: path 1->4->3
print(max_result([10,-5,-2,4,0,3], 3)) # 17: path 10->4->3
print(max_result([1,-5,-20,4,-1,3,-6,-3], 2)) # 0Maksimum w przesuwającym się oknie: alternatywa w postaci drzewa przedziałowego
W problemach, w których rozmiar okna zmienia się (nie jest stałą wartością k), monotoniczna kolejka dwustronna nie ma bezpośredniego zastosowania. Zamiast niej należy użyć rzadkiej tablicy do statycznych zapytań o maksimum z przedziału w czasie O(1) na zapytanie, po wstępnym przetworzeniu w czasie O(n log n), albo drzewa przedziałowego do dynamicznych aktualizacji, z czasem O(log n) na zapytanie. Jednak dla okien przesuwających się ze stałym k kolejka dwustronna jest bezkonkurencyjna dzięki złożoności O(n).
Podczas rozmów kwalifikacyjnych należy zawsze preferować monotoniczną kolejkę dwustronną O(n) zamiast drzewa przedziałowego O(n log n), gdy rozmiar okna jest stały. Należy wspomnieć o kompromisie: kolejka dwustronna nie obsługuje dowolnych rozmiarów okna ani aktualizacji, natomiast drzewa przedziałowe mogą je obsługiwać.
# Sparse table for static RMQ (range maximum query)
import math
def build_sparse_table(arr):
n = len(arr)
LOG = int(math.log2(n)) + 1 if n else 1
table = [[0]*n for _ in range(LOG)]
table[0] = arr[:]
j = 1
while (1 << j) <= n:
for i in range(n - (1 << j) + 1):
table[j][i] = max(table[j-1][i], table[j-1][i + (1 << (j-1))])
j += 1
return table
def query(table, l, r):
k = int(math.log2(r - l + 1))
return max(table[k][l], table[k][r - (1 << k) + 1])
arr = [1, 3, -1, -3, 5, 3, 6, 7]
table = build_sparse_table(arr)
k = 3
result = [query(table, i, i + k - 1) for i in range(len(arr) - k + 1)]
print('Sparse table result:', result) # [3, 3, 5, 5, 6, 7]Najdłuższa podtablica jedynek po usunięciu jednego elementu
LeetCode 1493: mając tablicę binarną, należy znaleźć długość najdłuższej podtablicy jedynek po usunięciu dokładnie jednego elementu (którym może być 0 lub 1). Jest to problem z użyciem przesuwającego się okna. Należy utrzymywać okno zawierające co najwyżej jedno 0. Gdy okno zawiera więcej niż jedno 0, trzeba zmniejszać je od lewej strony.
Wykorzystuje to schemat przesuwającego się okna o zmiennym rozmiarze, a nie kolejkę dwustronną. Można go jednak połączyć z techniką wyszukiwania okna o największym rozmiarze: po znalezieniu wszystkich poprawnych okien odpowiedzią jest ich maksymalna długość. „Usunięcie jednego elementu” oznacza, że w oknie jedynek dopuszczamy dokładnie jedno 0.
def longest_subarray(nums):
left = 0
zeros = 0
max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zeros += 1
while zeros > 1:
if nums[left] == 0:
zeros -= 1
left += 1
# Window [left, right] has at most 1 zero
# After deleting one element, length = right - left (not +1, since we delete one)
max_len = max(max_len, right - left)
return max_len
print(longest_subarray([1,1,0,1])) # 3: delete the 0
print(longest_subarray([0,1,1,1,0,1,1,0,1])) # 5
print(longest_subarray([1,1,1])) # 2: must delete one 1Porównanie deque, kolejki i stosu
Zrozumienie, kiedy używać poszczególnych kontenerów, ma kluczowe znaczenie podczas rozmów kwalifikacyjnych:
- Stos (list): LIFO, dostęp tylko z jednego końca. Należy go używać do DFS, analizowania wyrażeń i problemów z monotonicznym stosem.
- Kolejka (deque z appendleft/popleft): FIFO, dodawanie z jednego końca i usuwanie z drugiego. Należy jej używać do BFS i planowania zadań.
- Deque: dostęp do obu końców w czasie O(1). Należy jej używać w przesuwających się oknach z wygasaniem (usuwanie z początku) oraz z niezmiennikiem monotoniczności (usuwanie z końca). Maksimum w przesuwającym się oknie to klasyczny problem dla deque.
Element collections.deque w Pythonie jest narzędziem dla wszystkich trzech zastosowań. Należy używać append/pop do zachowania stosu oraz append/popleft lub appendleft/pop do zachowania kolejki albo deque.
from collections import deque
# deque as stack
stack = deque()
stack.append(1); stack.append(2); stack.append(3)
print('Stack pop:', stack.pop()) # 3 (LIFO)
# deque as queue
queue = deque()
queue.append(1); queue.append(2); queue.append(3)
print('Queue pop:', queue.popleft()) # 1 (FIFO)
# deque as sliding window with front expiry + back monotonic
dq = deque()
nums = [3, 1, 4, 1, 5, 9, 2, 6]
k = 3
for i, n in enumerate(nums):
while dq and dq[0] <= i - k: dq.popleft() # expire front
while dq and nums[dq[-1]] <= n: dq.pop() # maintain back
dq.append(i)
if i >= k - 1:
print(f'Window {nums[max(0,i-k+1):i+1]}: max={nums[dq[0]]}')Najkrótsza podtablica o sumie co najmniej K: deque + sumy prefiksowe
Najkrótsza podtablica o sumie co najmniej K (LeetCode 862) to zaawansowany problem łączący sumy prefiksowe z monotoniczną kolejką dwustronną. Należy zbudować sumy prefiksowe, a następnie użyć kolejki dwustronnej, aby dla każdego prawego końca znaleźć najbardziej lewą sumę prefiksową spełniającą warunek prefix[right] - prefix[left] >= k. Kolejka przechowuje rosnące sumy prefiksowe (elementy są usuwane z końca, aby zachować porządek rosnący), a elementy z początku są usuwane w celu zebrania poprawnych odpowiedzi.
Jest to jeden z najtrudniejszych problemów dotyczących przesuwającego się okna, ponieważ występują w nim liczby ujemne (co wyklucza proste podejście z dwoma wskaźnikami), a kolejka musi pełnić jednocześnie funkcję struktury monotonicznej i mechanizmu usuwania wygasłych elementów.
from collections import deque
def shortest_subarray(nums, k):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
dq = deque() # monotonic increasing deque of indices into prefix
result = float('inf')
for right in range(n + 1):
# Pop from front: valid subarrays ending at `right`
while dq and prefix[right] - prefix[dq[0]] >= k:
result = min(result, right - dq.popleft())
# Pop from back: maintain increasing deque
while dq and prefix[dq[-1]] >= prefix[right]:
dq.pop()
dq.append(right)
return result if result != float('inf') else -1
print(shortest_subarray([1], 1)) # 1
print(shortest_subarray([1, 2], 4)) # -1
print(shortest_subarray([2, -1, 2], 3)) # 3
print(shortest_subarray([84,-37,32,40,95], 167)) # 3Strategia rozwiązywania problemów z deque
Problem z monotoniczną kolejką dwustronną można rozpoznać po następujących sygnałach: (1) potrzebują Państwo maksimum lub minimum w przesuwającym się oknie o stałym rozmiarze, (2) potrzebują Państwo rekurencji DP dp[i] = f(nums[i], max(dp[i-k..i-1])) albo (3) potrzebują Państwo najbliższego poprawnego indeksu spełniającego warunek monotoniczności.
Podczas rozmów kwalifikacyjnych należy przejrzyście zaimplementować rozwiązanie z deque: zaimportować deque, utrzymywać dwa niezmienniki (wygasanie na początku i monotoniczność na końcu) oraz zwracać wyniki od indeksu k-1. Należy zawsze wspomnieć o złożoności czasowej O(n) i pamięciowej O(k) dla deque (jednocześnie przechowywanych jest najwyżej k indeksów) oraz porównać rozwiązanie z podejściem siłowym O(nk), aby pokazać uzyskaną poprawę.
from collections import deque
# Clean, interview-ready template
def sliding_window_max_template(nums, k):
if not nums or k == 0:
return []
dq = deque() # monotonic decreasing, stores indices
result = []
for i in range(len(nums)):
# Invariant 1: remove expired indices (outside window)
while dq and dq[0] < i - k + 1:
dq.popleft()
# Invariant 2: remove indices with smaller values (useless)
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# Record result once first full window is established
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Complexity: O(n) time, O(k) space
print(sliding_window_max_template([1,3,-1,-3,5,3,6,7], 3))
print(sliding_window_max_template([1], 1))
print(sliding_window_max_template([], 3))Szybki test
Sprawdź swoją znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: monotoniczna kolejka dwustronna malejąca utrzymuje maksimum okna na swoim początku, odrzucając z końca elementy mniejsze od nowo dodawanych, wygasłe indeksy są usuwane z początku, gdy znajdą się poza granicą okna oraz każdy indeks jest dodawany i usuwany najwyżej raz, co daje łączną złożoność O(n) i pamięć O(k) dla deque. Następnie rozwiążemy problem zbierania wody deszczowej, wykorzystując zarówno monotoniczny stos, jak i podejście z dwoma wskaźnikami.
Ucz się Coding Interview Prep dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 90
- Lekcje
- 360
Często zadawane pytania
Czy lekcja „Maksimum w oknie przesuwnym za pomocą monotonicznej kolejki dwustronnej” jest bezpłatna?
Tak — pełny tekst „Maksimum w oknie przesuwnym za pomocą monotonicznej kolejki dwustronnej” 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 oknie przesuwnym za pomocą monotonicznej kolejki dwustronnej”?
Utrzymywać malejącą kolejkę dwustronną indeksów, aby odpowiadać na zapytania o maksimum w oknie w czasie O(1) na element i rozwiązać problem sliding-window-maximum w czasie 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 3 z 4.
Ile czasu zajmuje lekcja „Maksimum w oknie przesuwnym za pomocą monotonicznej kolejki dwustronnej”?
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
- Stos monotoniczny: rosnący a malejący
- Największy prostokąt w histogramie
- Maksimum w oknie przesuwnym za pomocą monotonicznej kolejki dwustronnej
- Trapping Rain Water: stos i dwa wskaźniki