Sliding-window technique ni nini?

Question

Accepted Answer

Mbinu ya **sliding-window** inaendelea na eneo linaloendelea (dirisha) juu ya array au kamba na kuislide badala ya kuhesabu tena tangu mwanzo, na kutatua matatizo mengi ya subarray/substring katika **O(n)**.

## Wazo

Panua dirisha kwa kusogeza pembe ya kulia; kupunguza kwa kusogeza pembe ya kushoto wakati kizuizi kinakiwa kimekosewa. Tumia upya hesabu ya awali badala ya kusambaza tena.

## Mfano: jumla ya juu zaidi ya dirisha lolote la ukubwa 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)
```

## Utata

- **Wakati:** O(n) — kila kipengele kinaingia na kuacha dirisha mara moja.
- **Nafasi:** O(1) kwa dirisha dhuni, O(k) wakati wa kurekodi maudhui.

## Wakati wa kusanya / mitego

Tumia kwa matatizo "subarray mrefu zaidi/fupi zaidi/kubwa zaidi na sifa X". Kwa dirisha **linalobadilika**, songa kipointi cha kushoto kurejeza kizuizi. Onyo kwa makosa ya off-by-one wakati wa kuongeza/kuondoa vipengele vya mpaka.

## Kwa nini inastahili

Sliding window inaondoa kazi inayorudiwa, ikigeuza O(n·k) hesabu tena kuwa kwa kupitiwa mara moja.

Ni muundo wa kwa kawaida kwa matatizo ya substring na subarray yanayoonekana mara kwa mara katika mahojiano.

Maoni — tumia upya matokeo ya awali badala ya kuhesabu tena — inaeneza kwa mtiririko na data ya wakati halisi.