Co je technika posuvného okna?

Question

Accepted Answer

Technika **sliding-window** udržuje souvislý rozsah (okno) přes pole nebo řetězec a posouvá jej namísto opětovného počítání od nuly, řeší mnoho problémů s podpole/podřetězcem v **O(n)**.

## Myšlenka

Rozdeezte okno posunutím pravého okraje; zmenšete jej posunutím levého okraje, když je porušeno omezení. Znovu použijte předchozí výpočet místo opětovného prohledávání.

## Příklad: maximální součet jakéhokoli okna o 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)
```

## Složitost

- **Čas:** O(n) — každý prvek vstoupí a opustí okno jednou.
- **Prostor:** O(1) pro pevná okna, O(k) při sledování obsahu.

## Kdy použít / úskalí

Používejte pro problémy "nejdelší/nejkratší/max podpole s vlastností X". Pro **proměnné** okna posuňte levý ukazatel k obnovení omezení. Pozor na chyby off-by-one při přidávání/odebírání hraničních prvků.

## Proč to záleží

Posuvné okno eliminuje nadbytečnou práci, přeměňující přepočítání O(n·k) na jeden průchod.

Je to vzorový vzor pro problémy s podřetězcem a podpolem, které se neustále objevují v rozhovorech.

Myslenka — znovu použijte předchozí výsledek místo přepočítávání — se zobecňuje na streamování a data v reálném čase.