რა არის sliding-window ტექნიკა?

Question

Accepted Answer

**sliding-window** ტექნიკა ინარჩუნებს ერთმანეთის მომდევნო დიაპაზონს (window) მასივის ან სტრიქონის გასწვრივ და სლაიდ აკეთებს მას ნაცრიდან გადახრის ნაცვლად, მრავალი subarray/substring პრობლემის გადაჭრა **O(n)** დროში.

## იდეა

შეფართოვეთ window მარჯვენა კიდის მოძრაობით; შეკუმშეთ იგი მარცხენა კიდის მოძრაობით, როდესაც შეზღუდვა დაირღვევა. ხელახლა გამოიყენეთ წინა გამოთვლა ხელახლა სკანირების ნაცვლად.

## მაგალითი: 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)
```

## სირთულე

- **დრო:** O(n) — თითოეული ელემენტი ერთხელ შედის და ტოვებს window-ს.
- **სივრცე:** O(1) ფიქსირებული windows-ისთვის, O(k) როდესაც კონტენტი იკვებება.

## რა დროს გამოიყენოთ / მაზები

იყენეთ "ყველაზე გრძელი/ყველაზე მოკლე/მაქსიმალური subarray თვისებით X" პრობლემებისთვის. **ცვლადი** windows-ისთვის, გააძლიერეთ მარცხენა მაჩვენებელი შეზღუდვის აღსადგენად. ფრთხილად იყავით off-by-one შეცდომებთან საზღვრის ელემენტების დამატება/ამოღებისას.

## რატომ აქვს მნიშვნელობა

Sliding window აღმოფხვრის ზედმეტ ოპერაციას, ტრანსფორმირებს O(n·k) გადახრას ერთ გამოსახვაში.

ეს არის მთავარი ნიმუში substring და subarray პრობლემებისთვის, რომლებიც მუდმივად ჩნდებიან ინტერვიუებში.

ინტუიცია — წინა შედეგის ხელახლა გამოყენება ხელახლა გამოთვლის ნაცვლად — განზოგადდება streaming და real-time მონაცემებზე.