Overview
La technique de fenêtre glissante maintient une sous-séquence contiguë d'un tableau et la fait glisser pour résoudre des problèmes en O(n).
Analogy
Comme regarder par un cadre de fenêtre fixe qui glisse le long d'un panorama.
Step-by-step
- Définis la taille de la fenêtre ou la condition
- Initialise les résultats avec la première fenêtre
- Fais glisser : ajoute le nouvel élément, retire l'ancien
- Mets à jour le résultat optimal
Visual
nums=[2,1,5,1,3,2], k=3
[2,1,5]=8 → [1,5,1]=7 → [5,1,3]=9 → [1,3,2]=6
max=9
Common mistakes
- Recalculer toute la fenêtre à chaque étape (O(n²))
- Conditions d'extension/contraction de fenêtre incorrectes
Practice questions
- Trouve la sous-séquence de longueur k avec la somme maximale
- Trouve la plus longue sous-chaîne sans caractères répétés