Formations — 1 037 leçons en français

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²).

Lire l'explication détaillée et faire le quiz →

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.