Co to jest technika sliding-window?

Question

Accepted Answer

Technika **sliding-window** utrzymuje ciągły zakres (okno) na tablicy lub łańcuchu znakowym i przesuwa je zamiast przeliczać od nowa, rozwiązując wiele problemów z podtablicą/podłańcuchem w **O(n)**.

## Ideę

Rozwiń okno, przesuwając prawą krawędź; zmniejsz je, przesuwając lewą krawędź, gdy ograniczenie jest naruszane. Ponownie użyj poprzedniej obliczeń zamiast skanować od nowa.

## Przykład: maksymalna suma dowolnego okna o rozmiarze k

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## Złożoność

- **Czas:** O(n) — każdy element wchodzi i opuszcza okno raz.
- **Przestrzeń:** O(1) dla stałych okien, O(k) podczas śledzenia zawartości.

## Kiedy używać / pułapki

Używaj do problemów "najdłuższy/najkrótszy/maksymalny podtablica z właściwością X". W przypadku **zmiennych** okien, przesuń lewy wskaźnik, aby przywrócić ograniczenie. Uważaj na błędy off-by-one podczas dodawania/usuwania elementów granicznych.

## Dlaczego to ważne

Sliding window eliminuje zbędną pracę, zamieniając O(n·k) przeliczenie na jeden przebieg.

To szablon, który warto znać dla problemów substring i subarray, które ciągle pojawiają się w rozmowach kwalifikacyjnych.

Insight — ponownie użyj poprzedniego wyniku zamiast przeliczać — uogólnia się na streaming i dane w czasie rzeczywistym.