Mi a csúszó ablak (sliding-window) technika?

Question

Accepted Answer

A **sliding-window** (csúszó ablak) technika egy szomszédos tartományt (ablakot) tart fenn egy tömb vagy karakterlánc felett, és azt csúsztatja ahelyett, hogy nulláról kezdené újra a számítást, sok altömb/alkarakterlánc problémát **O(n)** időben megoldva.

## Az ötlet

Bővítsd az ablakot a jobb él mozgatásával; szűkítsd meg a bal él mozgatásával, ha egy feltétel megsérül. Használd újra az előző számítást ahelyett, hogy újraolvasnál.

## Példa: a k méretű ablak maximális összege

```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)
```

## Időbonyolultság

- **Idő:** O(n) — minden elem egyszer lép be és egyszer lép ki az ablakból.
- **Tér:** O(1) rögzített ablakok esetén, O(k) a tartalom nyomon követésekor.

## Mikor érdemes használni / buktatók

Használd a "leghosszabb/legrövidebb/maximális altömb X tulajdonsággal" típusú feladatokhoz. **Változó** ablakok esetén mozgasd előre a bal mutatót a feltétel helyreállításához. Vigyázz az off-by-one hibákra az elemek hozzáadásakor/eltávolításakor.

## Miért fontos

A csúszó ablak kiküszöböli a redundáns munkát, az O(n·k) újraszámítást egyetlen passzusra redukálva.

Ez az alapvető minta a karakterlánc és altömb problémákhoz, amelyek folyamatosan megjelennek az interjúkban.

A meglátás — az előző eredmény újrafelhasználása az újraszámítás helyett — általánosít a streaming és valós idejű adatokra.