Kayma penceresi (sliding-window) tekniği nedir?

Question

Accepted Answer

**Kayma penceresi** tekniği bir dizi veya dize üzerinde bitişik bir aralığı (pencere) korur ve sıfırdan yeniden hesaplamak yerine bunu kaydırarak birçok subarray/substring problemini **O(n)** içinde çözer.

## Fikir

Sağ kenarı hareket ettirerek pencereyi genişletin; bir kısıtlama ihlal edildiğinde sol kenarı hareket ettirerek daraltın. Tekrar tarama yerine önceki hesaplamayı yeniden kullanın.

## Örnek: k boyutunda herhangi bir pencerenin maksimum toplamı

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

## Karmaşıklık

- **Zaman:** O(n) — her öğe pencereye bir kez girer ve çıkar.
- **Alan:** Sabit pencereler için O(1), içeriği takip ederken O(k).

## Ne zaman kullanılır / tuzaklar

"X özelliğine sahip en uzun/en kısa/en büyük subarray" problemleri için kullanın. **Değişken** pencereler için kısıtlamayı geri yüklemek üzere sol işaretçiyi ileriye hareket ettirin. Sınır öğelerini eklerken/çıkarırken off-by-one hatalarına dikkat edin.

## Neden önemli

Kayma penceresi gereksiz işi ortadan kaldırır ve O(n·k) yeniden hesaplamayı tek bir geçişe dönüştürür.

Bu, mülakatlarda sürekli görünen substring ve subarray problemleri için standart yöntemdir.

Tasvir — yeniden hesaplamak yerine önceki sonucu yeniden kullanın — akış ve gerçek zamanlı veri işlemine genelleştirilir.