स्लाइडिंग-विंडो तंत्र म्हणजे काय?

Question

Accepted Answer

**स्लाइडिंग-विंडो** तंत्र एका अॅरे किंवा स्ट्रिंगवर एक सतत श्रेणी (विंडो) राखते आणि त्याला सर्वतः पुन्हा मोजण्याऐवजी स्लाइड करते, अनेक सबअॅरे/सबस्ट्रिंग समस्या **O(n)** मध्ये सोडवते।

## कल्पना

उजव्या किनारी हलवून विंडो विस्तृत करा; जेव्हा अडचण उल्लंघन होते तेव्हा डाव्या किनारी हलवून त्याचे संकोचन करा. पुनरावर्तन करण्याऐवजी मागील मोजणी पुनर्वापरा.

## उदाहरण: आकार 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) — प्रत्येक घटक विंडोमध्ये एकदा प्रवेश करतो आणि बाहेर पडतो.
- **स्पेस:** निश्चित विंडोसाठी O(1), सामग्री ट्रैक करताना O(k).

## कधी वापरायचे / त्रुटी

"गुणधर्म X असलेला सर्वात लांब/सर्वात लहान/कमाल सबअॅरे" समस्यांसाठी वापरा. **व्हेरिएबल** विंडोसाठी, अडचण पुनर्स्थापित करण्यासाठी डाव्या पॉइंटरला पुढे करा. सीमा घटक जोडताना/काढताना ऑफ-बाय-वन त्रुटीकडे लक्ष द्या.

## का महत्वाचे आहे

स्लाइडिंग विंडो अनावश्यक काम दूर करते, O(n·k) पुनर्गणना एका पुरातनमध्ये बदलते.

हे सबस्ट्रिंग आणि सबअॅरे समस्यांसाठी गो-टू पॅटर्न आहे जी मुलाखतीत सतत दिसून येते.

अंतर्दृष्टी — मागील परिणामाचा पुनर्वापर करा पुनर्गणना करण्याऐवजी — स्ट्रीमिंग आणि रीअल-टाइम डेटामध्ये सामान्यीकरण करते.