Çfarë është teknika e dritares rrëshqitëse?

Question

Accepted Answer

Teknika **e dritares rrëshqitëse** mendon një varg të vazhdueshëm (dritare) mbi një grup ose varg dhe e rrëshqet në vend që ta rillogarisë nga pika zero, duke zgjidhur shumë probleme subarray/substring në **O(n)**.

## Ideja

Zgjeroje dritaren duke lëvizur skajin e djathtë; zvogëloje atë duke lëvizur skajin e majtë kur një kufizim shkelohet. Ripërdor llogaritjen e mëparshme në vend të rivendosjes.

## Shembull: shuma maksimale e çdo dritareje me madhësi 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)
```

## Kompleksiteti

- **Koha:** O(n) — çdo element hyn dhe del nga dritarja një herë.
- **Hapësira:** O(1) për dritare fikse, O(k) kur gjurmoni përmbajtjen.

## Kur të përdorni / grackat

Përdorni për probleme "subarray më i gjatë/më i shkurtër/më i madh me vetinë X". Për dritare **të ndryshueshme**, lëvizni treguesin e majtë për të rivendosur kufizimin. Kujdes në gabimet off-by-one kur shtoni/hiqni elemente kufiri.

## Pse është e rëndësishme

Dritarja rrëshqitëse eliminon punën e tepërt, duke kthyer O(n·k) rillogaritjen në një kalim.

Eshtë modeli i parë për probleme substring dhe subarray që shfaqen vazhdimisht në interview.

Vëndimi — ripërdor rezultatin e mëparshëm në vend të rillogaritjes — përgjithësohet në rrjedhën dhe të dhënat në kohë reale.