Τι είναι η τεχνική sliding-window;

Question

Accepted Answer

Η τεχνική **sliding-window** διατηρεί ένα συνεχόμενο εύρος (παράθυρο) πάνω από ένα array ή string και το ολισθαίνει αντί να υπολογίζει από την αρχή, λύνοντας πολλά προβλήματα subarray/substring σε **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) κατά την παρακολούθηση του περιεχομένου.

## Πότε να χρησιμοποιήσετε / Παγίδες

Χρησιμοποιήστε για προβλήματα "μεγαλύτερο/μικρότερο/μέγιστο subarray με ιδιότητα X". Για **μεταβλητά** παράθυρα, προχωρήστε τον αριστερό δείκτη για να επαναφέρετε τον περιορισμό. Προσέξτε τα σφάλματα off-by-one κατά την προσθήκη/αφαίρεση στοιχείων ορίου.

## Γιατί έχει σημασία

Το sliding-window εξαλείφει περιττή εργασία, μετατρέποντας την επανυπολογισμό O(n·k) σε ένα πέρασμα.

Είναι το κύριο πρότυπο για προβλήματα substring και subarray που εμφανίζονται συνεχώς σε συνεντεύξεις.

Η διορατικότητα — επαναχρησιμοποιήστε το προηγούμενο αποτέλεσμα αντί να υπολογίσετε ξανά — γενικεύεται στη ροή και τα δεδομένα σε πραγματικό χρόνο.