Apakah itu teknik sliding-window?

Question

Accepted Answer

Teknik **sliding-window** mengekalkan satu julat bersebelahan (window) ke atas sesuatu array atau string dan menggelongsorkannya, bukannya mengira semula dari mula, lalu menyelesaikan banyak masalah subarray/substring dalam **O(n)**.

## Ideanya

Kembangkan window dengan menggerakkan tepi kanan; kecilkan ia dengan menggerakkan tepi kiri apabila sesuatu kekangan dilanggar. Guna semula pengiraan sebelumnya, bukannya mengimbas semula.

## Contoh: jumlah maksimum bagi mana-mana window bersaiz 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)
```

## Kompleksiti

- **Masa:** O(n) — setiap elemen masuk dan keluar dari window sekali sahaja.
- **Ruang:** O(1) bagi window tetap, O(k) apabila menjejak kandungan.

## Bila digunakan / perangkap

Guna untuk masalah "subarray terpanjang/terpendek/maksimum dengan sifat X". Bagi window **berubah-ubah**, gerakkan penunjuk kiri untuk memulihkan kekangan. Berhati-hati dengan ralat off-by-one apabila menambah/membuang elemen sempadan.

## Mengapa ia penting

Sliding window menghapuskan kerja berlebihan, menukar pengiraan semula O(n·k) kepada satu laluan sahaja.

Ia merupakan corak pilihan untuk masalah substring dan subarray yang sentiasa muncul dalam temu duga.

Ideanya — guna semula keputusan sebelumnya, bukannya mengira semula — boleh diperluaskan kepada data streaming dan masa nyata.