Što je sliding-window (klizajući prozor) tehnika?

Question

Accepted Answer

**Sliding-window** tehnika održava neprekidni raspon (prozor) preko niza ili string-a i klizi kroz njega umjesto da ponovo računa od početka, rješavajući mnoge probleme sa subnizovima/podstringovima u **O(n)**.

## Osnovni koncept

Proširite prozor pomicanjem desne granice; skupite ga pomicanjem lijeve granice kada je ograničenje narušeno. Ponovno iskoristite prethodnu računicu umjesto da ponovno skenirate.

## Primjer: maksimalna suma bilo kojeg prozora veličine 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)
```

## Vremenska složenost

- **Vrijeme:** O(n) — svaki element uđe i izađe iz prozora jednom.
- **Prostor:** O(1) za fiksirane prozore, O(k) kada pratite sadržaj.

## Kada koristiti / zamke

Koristite za probleme "najduži/najkraći/maksimalni podniz sa svojstvom X". Za **varijabilne** prozore, pomakните lijevu pokazivač kako biste obnovili ograničenje. Pazite na greške za jedan (off-by-one) pri dodavanju/uklanjanju graničnih elemenata.

## Zašto je važno

Klizajući prozor eliminira suvišan rad, pretvarajući O(n·k) ponovnu računicu u jedan prolaz.

To je osnovni uzorak za probleme sa stringovima i subnizovima koji se stalno pojavljuju na razgovorima za posao.

Insight — ponovno iskoristite prethodni rezultat umjesto da ponovo računate — generalizira se na streaming i podatke u realnom vremenu.