Accueil › Coding & algorithmique › La fenêtre glissante
La fenêtre glissante
Tableaux et parcoursdebutant
La fenêtre glissante résout les énoncés « la plus longue / la plus courte suite contiguë qui… » en O(n).
Taille fixe — un entre, un sort :
// Somme maximale de k éléments consécutifs
static int sommeMaxK(int[] t, int k) {
int somme = 0;
for (int i = 0; i < k; i++) somme += t[i];
int meilleur = somme;
for (int i = k; i < t.length; i++) {
somme += t[i] - t[i - k]; // glissement en O(1)
meilleur = Math.max(meilleur, somme);
}
return meilleur;
}
Taille variable — étendre à droite, rétrécir à gauche :
// Plus petit sous-tableau de somme ≥ cible (valeurs positives)
static int plusPetitSousTableau(int[] t, int cible) {
int g = 0, somme = 0, meilleur = Integer.MAX_VALUE;
for (int d = 0; d < t.length; d++) {
somme += t[d];
while (somme >= cible) { // tant que la fenêtre est valide
meilleur = Math.min(meilleur, d - g + 1);
somme -= t[g++]; // on rétrécit pour chercher plus court
}
}
return meilleur == Integer.MAX_VALUE ? 0 : meilleur;
}
La question qui revient toujours : pourquoi cette double boucle est-elle en O(n) ? Parce que g n'avance jamais en arrière. Sur toute l'exécution, il progresse au plus n fois. Chaque élément entre une fois et sort au plus une fois : 2n opérations. Savoir expliquer ce raisonnement amorti vaut autant que le code.
Les termes à connaître
- Fenêtre glissante
Deux indices délimitant une plage contiguë qu'on étend à droite et rétrécit à gauche, sans jamais revenir en arrière. Chaque élément entre et sort au plus une fois : O(n).
- Fenêtre de taille fixe
La plage garde une largeur constante k. À chaque pas, un élément entre et un sort : la mise à jour est en O(1).
- Fenêtre de taille variable
La plage s'étend tant que la condition tient, se rétrécit quand elle est violée. Sert aux énoncés « la plus longue » ou « la plus courte » sous contrainte.
- État de la fenêtre
L'information maintenue au fil du glissement : somme, compteur de caractères, nombre de valeurs distinctes. Elle doit se mettre à jour en O(1) à l'entrée et à la sortie.
- Invariant de fenêtre
La propriété vraie à chaque tour : « la fenêtre [g, d] ne contient aucun doublon ». L'énoncer avant d'écrire évite la plupart des bugs.
- Amortissement
Le bord gauche avance au total n fois sur l'ensemble de l'exécution, même s'il bouge plusieurs fois dans un tour. D'où une complexité globale en O(n), pas en O(n²).
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.