Qu'est-ce que la technique de la fenêtre glissante ?

Question

Accepted Answer

La technique de la **fenêtre glissante** maintient une plage contiguë (fenêtre) sur un tableau ou une chaîne de caractères et la fait glisser au lieu de recalculer à partir de zéro, résolvant de nombreux problèmes de sous-tableau/sous-chaîne en **O(n)**.

## L'idée

Élargissez la fenêtre en déplaçant le bord droit ; rétrécissez-la en déplaçant le bord gauche quand une contrainte est violée. Réutilisez le calcul précédent au lieu de rescanner.

## Exemple : somme maximale de toute fenêtre de taille 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)
```

## Complexité

- **Temps :** O(n) — chaque élément entre et quitte la fenêtre une fois.
- **Espace :** O(1) pour les fenêtres fixes, O(k) quand on suit le contenu.

## Quand l'utiliser / pièges

Utilisez-la pour les problèmes « plus long/plus court/max sous-tableau avec propriété X ». Pour les fenêtres **variables**, avancez le pointeur gauche pour restaurer la contrainte. Attention aux erreurs hors de un quand on ajoute/supprime les éléments limites.

## Pourquoi c'est important

La fenêtre glissante élimine le travail redondant, transformant le recalcul O(n·k) en une seule passe.

C'est le motif incontournable pour les problèmes de sous-chaîne et de sous-tableau qui apparaissent constamment dans les entretiens.

L'intuition — réutiliser le résultat précédent au lieu de recalculer — se généralise au streaming et aux données en temps réel.