Kaj je tehnika drsečega okna?

Question

Accepted Answer

Tehnika **drsečega okna** vzdržuje contiguous razpon (okno) čez polje ali niz in ga drsi namesto da bi ponovnega izračuna iz začetka, kar reši många nalog s subarray/substring v **O(n)**.

## Ideja

Razvij okno z premikanjem desnega roba; krči ga z premikanjem levega roba, kadar je omejitev kršena. Ponovno uporabi prejšnji izračun namesto da bi ponovno skeniral.

## Primer: največja vsota kateregakoli okna velikosti 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)
```

## Kompleksnost

- **Čas:** O(n) — vsak element vstopi in zapusti okno enkrat.
- **Prostor:** O(1) za fiksna okna, O(k) pri sledenju vsebini.

## Kdaj uporabiti / pasti

Uporabi za probleme "najdaljši/najkrajši/največji subarray s lastnostjo X". Za **spremenljiva** okna premakni levi kazalec, da obnoviš omejitev. Pazi na off-by-one napake pri dodajanju/odstranitvi mejnih elementov.

## Zakaj je to pomembno

Drsečo okno odstrani redundantno delo, kar preimenuje O(n·k) ponovno izračuno v en prehod.

To je osrednji vzorec za probleme substring in subarray, ki se neprestano pojavljajo na razgovorih.

Vpogled — ponovno uporabi prejšnji rezultat namesto da bi ponovno računal — se posploši na pretakanje in podatke v realnem času.