Sliding window to wzorzec algorytmiczny, który redukuje wiele problemów typu „znajdź najdłuższe / najmniejsze / najlepsze contiguous subarray" z O(n²) do O(n). Zamiast sprawdzać każde możliwe podtablicy oddzielnie, algorytm utrzymuje okno o zmiennym lub stałym rozmiarze, które przesuwa się po danych.
W tym artykule pokazuję trzy warianty: fixed-size (okno o stałej długości K), variable-size (rozszerza/kurczy się dynamicznie), oraz monotonic deque (zaawansowany wariant dla sliding window maximum). Każdy z trace step-by-step, sygnałami rozpoznawczymi i mechanizmami pułapek. Implementacje w Pythonie dla zwięzłości — wzorzec jest language-agnostic.
Pozostaję w obrębie czystego sliding window. Two pointers (też dwa wskaźniki, ale bez koncepcji „okna" jako spójnego stanu) to powiązany ale osobny temat — szczegóły: Two Pointers.
Czym jest sliding window — definicja + ASCII
Sliding window, czyli okno przesuwne, to technika pracy na ciągłym fragmencie danych: contiguous subarray w tablicy albo contiguous substring w stringu. Zamiast budować każdy możliwy fragment od zera, utrzymujesz dwa końce okna, najczęściej left i right, oraz stan tego, co znajduje się pomiędzy nimi.
Intuicja jest prosta: okno obejmuje aktualnie interesujący zakres, a potem przesuwa się po danych, aktualizując wynik lokalnie.
array: [2, 1, 5, 1, 3, 2]
index: 0 1 2 3 4 5
window size 3:
[2, 1, 5]
[1, 5, 1]
[5, 1, 3]
[1, 3, 2]
Sygnał rozpoznawczy: problem pyta o najdłuższy, najkrótszy, maksymalny, minimalny albo liczony fragment ciągły. Jeżeli elementy nie muszą leżeć obok siebie, to zwykle nie jest sliding window, tylko DP, backtracking, greedy albo inna technika.
def window_sums(values, size):
total = sum(values[:size])
result = [total]
for right in range(size, len(values)):
total += values[right] - values[right - size]
result.append(total)
return result
print(window_sums([2, 1, 5, 1, 3, 2], 3)) # expected_output: [8, 7, 9, 6]
Trace:
1. Start: okno [2, 1, 5], suma 8.
2. Przesunięcie o jeden: dodaj 1, usuń 2, suma 7.
3. Przesunięcie o jeden: dodaj 3, usuń 1, suma 9.
4. Przesunięcie o jeden: dodaj 2, usuń 5, suma 6.
Pułapka: sliding window nie oznacza „dowolne dwa indeksy”. Mechanizm działa dlatego, że zakres jest ciągły i możesz przewidywalnie usuwać element opuszczający okno oraz dodawać element wchodzący do okna.
Fixed-size window — okno o stałym rozmiarze K
Fixed-size window stosujesz wtedy, gdy długość okna jest dana z góry: na przykład „maksymalna suma K kolejnych elementów” albo „średnia z każdego fragmentu długości K”. Okno ma zawsze ten sam rozmiar, więc oba pointery przesuwają się razem o 1.
Intuicja: pierwszy wynik liczysz normalnie, a potem każde kolejne okno różni się tylko dwoma elementami. Jeden element wypada z lewej strony, jeden wchodzi z prawej.
k = 3
[4, 2, 1, 7, 8]
L R
L R
L R
Spotkasz to w zadaniach z frazami typu: „exactly K”, „subarray of size K”, „maximum average subarray”, „K consecutive elements”. Wersja brute force liczy każde okno osobno w O(n*k), a sliding window sprowadza to do O(n).
def max_sum_fixed(values, size):
current = sum(values[:size])
best = current
for right in range(size, len(values)):
current += values[right] - values[right - size]
best = max(best, current)
return best
print(max_sum_fixed([4, 2, 1, 7, 8], 3)) # expected_output: 16
Trace:
1. Pierwsze okno [4, 2, 1], suma 7, najlepsza 7.
2. Okno [2, 1, 7]: dodaj 7, usuń 4, suma 10.
3. Okno [1, 7, 8]: dodaj 8, usuń 2, suma 16.
4. Wynik końcowy to 16.
Pułapka: częsty błąd to przesuwanie tylko right i zapominanie o usunięciu elementu z lewej. W fixed window rozmiar musi zostać równy K; inaczej algorytm przypadkiem zmienia się w variable window.
Variable-size window — okno rośnie/kurczy się dynamicznie
Variable-size window ma długość zależną od warunku. right rozszerza okno, a left kurczy je wtedy, gdy warunek zostanie złamany. Klasyczny przykład to longest substring without repeating characters: szukasz najdłuższego ciągłego fragmentu bez powtórek.
Intuicja: okno reprezentuje aktualny poprawny kandydat. Gdy dodanie nowego znaku psuje warunek, przesuwasz lewy koniec tak długo, aż okno znów będzie poprawne.
s = "abca"
right dodaje 'a', 'b', 'c':
[a b c] a
right dodaje drugie 'a', warunek złamany:
[a b c a]
^ usuń od lewej do odzyskania poprawności
Sygnał rozpoznawczy: problem mówi o „longest”, „shortest”, „at most K”, „no repeats”, „sum at least target” albo „while condition is invalid”. Do śledzenia stanu okna często używa się set albo collections.Counter.
def longest_unique(text):
seen = set()
left = 0
best = 0
for right, char in enumerate(text):
while char in seen:
seen.remove(text[left])
left += 1
seen.add(char)
best = max(best, right - left + 1)
return best
print(longest_unique("abcabcbb")) # expected_output: 3
Trace:
1. a, b, c wchodzą do okna: "abc", wynik 3.
2. Drugie a łamie warunek, więc usuwasz stare a.
3. Okno staje się "bca", nadal długość 3.
4. Kolejne powtórki wymuszają dalsze kurczenie, ale wynik nie przekracza 3.
Pułapka: nie wystarczy wykryć duplikatu i przesunąć left raz. Duplikat może nadal być w oknie, więc mechanizm musi kurczyć okno w pętli while, aż warunek naprawdę będzie spełniony.
Wzorzec expand/shrink — gdy warunek spełniony rozszerz, gdy złamany skurcz
Expand/shrink to praktyczny szablon dla zmiennego okna. right prawie zawsze idzie w jednej pętli od lewej do prawej, dodając element do stanu. Gdy stan przestaje spełniać warunek, left usuwa elementy aż do naprawienia okna.
Intuicja działania opiera się na monotonicznym ruchu pointerów. right nigdy się nie cofa, left też nigdy się nie cofa. Dlatego złożoność wynosi O(n): każdy element wchodzi do okna maksymalnie raz i wychodzi z niego maksymalnie raz.
expand:
left right
v v
[ valid window ... new item ]
shrink:
left ->
usuń elementy, aż okno znów będzie valid
Ten wzorzec spotkasz przy ograniczeniach typu „co najwyżej K różnych znaków”, „suma mniejsza niż X”, „produkt mniejszy niż K”. Ważne: dla sum z liczbami ujemnymi klasyczne kurczenie po przekroczeniu progu może przestać działać.
def longest_at_most_k_distinct(text, limit):
counts = {}
left = 0
best = 0
for right, char in enumerate(text):
counts[char] = counts.get(char, 0) + 1
while len(counts) > limit:
old = text[left]
counts[old] -= 1
if counts[old] == 0:
del counts[old]
left += 1
best = max(best, right - left + 1)
return best
print(longest_at_most_k_distinct("eceba", 2)) # expected_output: 3
Trace:
1. "e" i "ec" są poprawne, bo mają najwyżej 2 różne znaki.
2. "ece" nadal jest poprawne, wynik 3.
3. Dodanie "b" daje trzy różne znaki, więc przesuwasz left.
4. Po usunięciu starego "e" okno znów spełnia limit.
Pułapka: if len(counts) > limit bywa niewystarczające. Po jednym przesunięciu left warunek nadal może być złamany, dlatego poprawny mechanizm używa while.
Trace dla longest substring without repeating characters
Problem: dla stringa zwróć długość najdłuższego ciągłego fragmentu bez powtarzających się znaków. Sliding window pasuje idealnie, bo interesuje nas contiguous substring, a warunek poprawności zależy od zawartości aktualnego okna.
Intuicja: set przechowuje znaki w bieżącym oknie. Jeśli right wskazuje znak, którego jeszcze nie ma, rozszerzasz okno. Jeśli znak już istnieje, usuwasz znaki od lewej, aż konflikt zniknie.
s = "pwwkew"
p -> valid
pw -> valid
pww -> invalid, duplicate w
w -> valid after shrink
wk -> valid
wke -> valid
kew -> valid
Sygnał rekrutacyjny: zadanie wygląda jak problem o substringach, ale brute force sprawdzałby wiele fragmentów od zera. Sliding window utrzymuje stan i naprawia tylko aktualne okno.
def longest_unique_length(text):
seen = set()
left = 0
best = 0
for right, char in enumerate(text):
while char in seen:
seen.remove(text[left])
left += 1
seen.add(char)
best = max(best, right - left + 1)
return best
print(longest_unique_length("pwwkew")) # expected_output: 3
Trace:
1. right=0, znak p, okno "p", best=1.
2. right=1, znak w, okno "pw", best=2.
3. right=2, znak w już istnieje; usuń p, potem stare w.
4. Okno po dodaniu nowego w to "w", best=2.
5. Dodaj k, potem e: okno "wke", best=3.
6. Dodaj w; usuń znaki od lewej do usunięcia konfliktu, okno "kew".
Pułapka: jeśli używasz mapy last_seen, nie cofaj left. Poprawne przesunięcie to left = max(left, last_seen[char] + 1), bo ostatnia pozycja znaku może leżeć poza aktualnym oknem.
Z deque — sliding window maximum
Sliding window maximum pyta o maksimum w każdym oknie długości K. Naiwne rozwiązanie sprawdza maksimum dla każdego okna osobno, co daje O(n*k). Optymalne rozwiązanie używa deque jako kolejki monotonicznej.
Intuicja: deque trzyma indeksy elementów w monotonicznym porządku wartości, zwykle malejąco. Przód deque jest indeksem największego elementu w aktualnym oknie. Z tyłu usuwasz indeksy elementów mniejszych od nowego, bo nie będą już kandydatami na maksimum.
values = [1, 3, -1, -3, 5], k = 3
deque stores indexes, values decreasing:
indexes: [1, 2]
values: [3, -1]
max = values[1] = 3
Sygnał rozpoznawczy: problem pyta o max/min dla każdego ciągłego okna, a K może być duże. Monotonic deque daje O(n) total, bo każdy indeks jest dodany raz i usunięty najwyżej raz.
from collections import deque
def sliding_max(values, size):
queue = deque()
result = []
for right, value in enumerate(values):
while queue and queue[0] <= right - size:
queue.popleft()
while queue and values[queue[-1]] <= value:
queue.pop()
queue.append(right)
if right >= size - 1:
result.append(values[queue[0]])
return result
print(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3)) # expected_output: [3, 3, 5, 5, 6, 7]
Trace:
1. Dla [1, 3, -1] deque wskazuje 3, wynik 3.
2. Przy przesunięciu do [3, -1, -3] maksimum nadal 3.
3. Gdy wchodzi 5, usuwa z tyłu mniejsze wartości, więc maksimum to 5.
4. Gdy wchodzą 6 i 7, każdy usuwa słabszych kandydatów z tyłu.
Pułapka: deque powinien trzymać indeksy, nie same wartości. Indeksy pozwalają sprawdzić, czy element wypadł poza okno; bez nich łatwo zostawić stare maksimum, które nie należy już do aktualnego zakresu.
Sliding window vs two pointers — kiedy która technika
Sliding window jest blisko spokrewnione z two pointers, ale nie jest tym samym tematem. Sliding window utrzymuje stan ciągłego fragmentu: sumę, licznik znaków, set, Counter, deque albo inną strukturę opisującą zakres left..right.
Intuicja kontrastu: w two pointers wskaźniki często pracują na posortowanej tablicy z dwóch stron, na przykład przy two sum w sorted array. W sliding window pointery opisują granice okna, które przesuwa się po sąsiednich elementach.
sliding window:
[ a b c d e ]
L R contiguous state
two pointers:
[ a b c d e ]
L R compare pair, often sorted input
W rozmowie technicznej użyj sliding window, gdy pytanie dotyczy ciągłego fragmentu i lokalnego warunku. Użyj two pointers, gdy chodzi o parę, scalanie, partition, sorted input albo porównywanie elementów z krańców.
def has_pair_sum(sorted_values, target):
left = 0
right = len(sorted_values) - 1
while left < right:
total = sorted_values[left] + sorted_values[right]
if total == target:
return True
if total < target:
left += 1
else:
right -= 1
return False
print(has_pair_sum([1, 2, 4, 7, 11], 9)) # expected_output: True
Trace:
1. Sprawdź 1 + 11 = 12, za dużo, więc zmniejsz right.
2. Sprawdź 1 + 7 = 8, za mało, więc zwiększ left.
3. Sprawdź 2 + 7 = 9, znaleziono parę.
4. To nie jest sliding window, bo nie utrzymujesz stanu ciągłego zakresu.
Pułapka: nie nazywaj każdego rozwiązania z dwoma indeksami sliding window. Mechanizm sliding window polega na aktualizacji stanu okna, a nie tylko na tym, że w kodzie występują left i right.
Sygnały rozpoznawcze: kiedy sliding window
Sliding window rozpoznasz po połączeniu dwóch słów-kluczy: ciągły fragment oraz warunek lokalny. Fragment musi być contiguous: podtablica, substring, kolejne elementy, zakres długości K, minimalny fragment spełniający próg.
Intuicja: jeśli po przesunięciu granicy możesz tanio zaktualizować stan, to prawdopodobnie masz okno. Stanem może być suma, liczba różnych znaków, set powtórek, Counter częstotliwości albo monotonic deque dla maksimum/minimum.
Dobre sygnały:
- longest substring ...
- subarray of size K
- minimum length subarray ...
- at most K distinct
- maximum in every window
Na LeetCode i w materiałach typu Real Python ten wzorzec pojawia się jako sposób zastępowania sprawdzania wszystkich fragmentów aktualizacją jednego bieżącego zakresu. Dla zliczania znaków w Pythonie przydatny jest collections.Counter, który według dokumentacji Pythona służy do liczenia obiektów hashowalnych.
from collections import Counter
def has_permutation(text, pattern):
size = len(pattern)
target = Counter(pattern)
window = Counter(text[:size])
if window == target:
return True
for right in range(size, len(text)):
window[text[right]] += 1
window[text[right - size]] -= 1
if window[text[right - size]] == 0:
del window[text[right - size]]
if window == target:
return True
return False
print(has_permutation("eidbaooo", "ab")) # expected_output: True
Trace:
1. Cel to częstotliwości znaków w "ab".
2. Pierwsze okno długości 2 to "ei", nie pasuje.
3. Kolejne okna aktualizują Counter: dodaj znak z prawej, usuń znak z lewej.
4. Okno "ba" ma ten sam licznik co "ab", więc wynik to True.
Pułapka: sliding window wymaga, aby stan dało się poprawnie aktualizować po usunięciu lewego elementu. Jeśli po usunięciu nie umiesz odtworzyć informacji taniej niż przeliczeniem całego okna, potrzebujesz innej struktury albo innego algorytmu.
Kiedy NIE sliding window — anti-przykład
Nie używaj sliding window, gdy fragment nie musi być ciągły. Jeśli zadanie pyta o subsequence, wybór dowolnych elementów, plecak, LIS albo optymalny podzbiór, okno przesuwne zwykle nie pasuje. Sliding window operuje na contiguous subarray/substring.
Intuicja: okno działa, bo przesuwasz granice i zachowujesz kolejność oraz sąsiedztwo. Gdy wolno pomijać elementy, „lewy element wychodzi, prawy wchodzi” przestaje opisywać przestrzeń decyzji.
Nie sliding window:
array = [3, 10, 2, 1, 20]
LIS = [3, 10, 20] albo [2, 20]
Wybrane elementy nie muszą tworzyć jednego ciągłego okna.
Anti-przykłady: range query po posortowanych danych często rozwiązuje się przez bisect, a problemy non-contiguous przez DP. Jeśli pytanie brzmi „ile liczb mieści się w przedziale wartości”, a nie „jaki jest ciągły fragment tablicy”, sliding window może być sztucznym dopasowaniem.
from bisect import bisect_left, bisect_right
def count_in_range(sorted_values, low, high):
left = bisect_left(sorted_values, low)
right = bisect_right(sorted_values, high)
return right - left
print(count_in_range([1, 3, 3, 5, 8, 13], 3, 8)) # expected_output: 4
Trace:
1. Dane są posortowane, więc pytanie dotyczy zakresu wartości, nie okna indeksów.
2. bisect_left znajduje pierwszą pozycję >= 3.
3. bisect_right znajduje pierwszą pozycję > 8.
4. Różnica indeksów daje liczbę elementów w zakresie.
Pułapka: „range” w treści zadania nie zawsze oznacza sliding window. Jeśli zakres dotyczy wartości, zapytań albo nieciągłego wyboru, mechanizm okna może być błędny. Źródła i analogie: LeetCode sliding window patterns, Real Python patterns, Wikipedia Sliding window protocol jako analogia przesuwania zakresu oraz docs.python.org dla collections.Counter.
Najczęstsze błędy
Sliding window na non-contiguous data. Sliding window działa tylko na podtablicach/podciągach — elementy muszą być sąsiednie. Mechanizm błędu: kandydat próbuje sliding window dla „longest increasing subsequence" (gdzie elementy mogą pomijać pozycje) — wzorzec się załamuje. Naprawa: dla non-contiguous użyj DP albo bisect na patience sort.
Brak aktualizacji okna przy shrink. Dla variable-size: gdy left przesuwa się w prawo, musisz zaktualizować stan okna (usunąć data[left] z counter/set). Mechanizm błędu: stan reprezentuje stare okno + nowe elementy = niepoprawny. Naprawa: zawsze symetrycznie aktualizuj — add(data[right]) przy expand, remove(data[left]) przy shrink.
Off-by-one przy obliczaniu długości okna. right - left + 1 to długość okna (włącznie z oboma końcami). Mechanizm błędu: kandydat pisze right - left i otrzymuje wynik o 1 za mały. Naprawa: zapamiętaj wzór [left, right] (closed) → length = right - left + 1; [left, right) (half-open) → length = right - left.
Sliding window maximum z naive max(). Bez monotonic deque dla każdego okna wywołujesz max(window) w O(k) — total O(n*k), nie O(n). Mechanizm błędu: dla n=10⁵, k=100 różnica między O(n) a O(n*k) to 10⁷ vs 10⁷ operacji — niezauważalne dla małych, dramatyczne dla k=10⁴. Naprawa: monotonic deque utrzymuje kandydatów na max, każdy element wchodzi/wychodzi raz.
Mylenie sliding window z two pointers. Two pointers (opposite-direction) idą do siebie z końców na sorted data. Sliding window oba pointery idą w tę samą stronę i utrzymują „okno" — stan między nimi. Mechanizm błędu: kandydat używa nazwy zamiennie, na rozmowie rozmówca prosi o jeden, kandydat opisuje drugi. Naprawa: same-direction + spójne okno = sliding window; opposite-direction lub fast/slow = two pointers.
FAQ
Czy sliding window zawsze daje O(n)?
Tak dla podstawowych wariantów (fixed-size, simple variable-size). Każdy element wchodzi do okna raz i wychodzi maksymalnie raz, więc total moves = 2n = O(n). Wyjątki: gdy aktualizacja stanu okna jest O(k) (np. szukanie max bez monotonic deque), całkowity koszt rośnie do O(n*k). Sliding window maximum z monotonic deque pozostaje O(n).
Co to monotonic deque?
Deque (kolejka dwustronna) utrzymujący elementy w monotonicznym porządku (np. malejącym dla sliding window maximum). Przy dodawaniu nowego elementu usuwasz z prawej strony wszystkie mniejsze (nie mogą być max gdy nowy jest większy). Przy expirze okna usuwasz z lewej strony jeśli indeks za stary. Każdy element wchodzi/wychodzi maksymalnie raz → amortyzowane O(1) per krok. Szczegóły deque: Stos i Kolejka.
Sliding window czy hash map dla „longest substring without repeats"?
Oba używają hash mapy/setu, ale różnią się intuicją. Sliding window: dwa wskaźniki, expand/shrink, śledź last_seen[char]. Hash map alone: dla każdego startu próbuj rozszerzać → O(n²). Standardowa odpowiedź to sliding window + hash map jako stan okna — O(n) czas, O(min(n, alphabet)) pamięć. Szczegóły hash: Haszowanie w Zadaniach.
Jak wybrać między fixed a variable window?
Fixed gdy zadanie podaje konkretne K („max sum of K consecutive", „average of K"). Variable gdy zadanie pyta o najdłuższe / najmniejsze / pierwsze spełniające warunek („longest substring with at most 2 distinct", „smallest window containing all chars from T"). Variable rozszerzasz aż warunek złamany, kurczysz aż znów spełniony.
Czy sliding window działa na 2D (matrycach)?
Tak, ale rzadziej spotykane. 2D sliding window to okno o rozmiarze m×n przesuwane po macierzy M×N. Czas O(M*N) dla fixed-size przy odpowiednim summed area table. Częściej w praktyce — image processing (convolution to 2D sliding window z agregacją). Na rozmowie raczej 1D, chyba że zadanie wprost o macierze.
Z czego korzystać do śledzenia stanu okna — set, dict, czy Counter?
Set gdy interesuje cię tylko obecność (longest substring with unique chars). Dict gdy potrzebujesz dodatkowej informacji per klucz (last index seen). Counter gdy liczysz wystąpienia (window with at most K distinct chars). Reguła: minimalna struktura która odpowiada na twoje pytania o stan okna.
Powiązane tematy
- Two Pointers — Wzorzec Dwóch Wskaźników — pokrewny wzorzec z dwoma wskaźnikami; różnica: two pointers nie utrzymują „okna" jako spójnego stanu.
- Stos i Kolejka — LIFO i FIFO —
collections.dequejako monotonic deque dla sliding window maximum wO(n). - Haszowanie w Zadaniach — Wzorzec na Rozmowie — hash map/Counter jako stan okna dla problemów z duplikatami i frequency.
Sprawdź swoją wiedzę quizem
Przerób ten artykuł w 15-pytaniowy quiz testujący fixed/variable window, expand/shrink, longest substring i monotonic deque: https://odpytywarka.pl/q/pBrAH0.
Masz własne notatki na rozmowę? Wgraj PDF lub wklej tekst na stworz-quiz-z-pdf — pierwsze 3 strony PDF i 15 pytań jednokrotnego wyboru za darmo, generowanie 30-60 sekund.
Źródła
- Python
collections.deque— kolejka dwustronna dla monotonic deque - Python
collections.Counter— frequency counter dla stanu okna - Big O notation — Wikipedia — formal definition złożoności
- Real Python — Sliding window patterns — praktyczne zastosowania