04 — La fenêtre glissante

Ce que tu vas apprendre

• Le principe de la fenêtre glissante et pourquoi elle évite le recalcul
• La fenêtre de taille fixe : moyenne mobile, somme maximale
• La fenêtre de taille variable : plus longue sous-chaîne sous contrainte
• Comment reconnaître un problème de fenêtre glissante

Prérequis

• 03 — Le pattern des deux pointeurs

La fenêtre glissante est une spécialisation des deux pointeurs, dédiée aux problèmes portant sur un sous-tableau ou une sous-chaîne contigus. L'idée centrale : quand la fenêtre avance d'un cran, on ne recalcule pas tout son contenu, on retire l'élément qui sort et on ajoute celui qui entre. Ce simple changement transforme un O(n²) en O(n).

Le gâchis du recalcul

Prenons un problème type : trouver la somme maximale d'un sous-tableau de taille k. L'approche naïve calcule la somme de chaque fenêtre de k éléments à partir de zéro.

typescript// O(n × k) : on resomme toute la fenêtre à chaque position
function sommeMaxNaif(arr: number[], k: number): number {
  let max = -Infinity;
  for (let i = 0; i + k <= arr.length; i++) {
    let somme = 0;
    for (let j = i; j < i + k; j++) somme += arr[j]; // recalcul complet
    max = Math.max(max, somme);
  }
  return max;
}

À chaque position, on resomme k éléments, dont k - 1 étaient déjà dans la fenêtre précédente. C'est du gâchis. La fenêtre glissante l'élimine.

La fenêtre de taille fixe

On calcule la somme de la première fenêtre, puis on fait glisser : à chaque pas, on soustrait l'élément qui sort à gauche et on ajoute celui qui entre à droite.

pythondef somme_max(arr: list[int], k: int) -> int:
    somme = sum(arr[:k])          # première fenêtre, une fois
    maximum = somme
    for i in range(k, len(arr)):
        somme += arr[i] - arr[i - k]  # entre arr[i], sort arr[i-k]
        maximum = max(maximum, somme)
    return maximum

Chaque élément entre une fois et sort une fois dans la fenêtre : O(n). On est passé de O(n × k) à O(n). C'est la base des moyennes mobiles utilisées partout en traitement de signal et en analyse de séries temporelles.

La fenêtre de taille variable

Le cas le plus puissant : la fenêtre grandit et rétrécit selon une contrainte. On étend la fenêtre par la droite tant que la contrainte tient, et on la rétrécit par la gauche quand elle est violée. Problème classique : la plus longue sous-chaîne sans caractère répété.

pythondef plus_longue_sans_repetition(s: str) -> int:
    vus = {}                  # caractère -> dernière position
    gauche = 0
    meilleur = 0
    for droite, c in enumerate(s):
        if c in vus and vus[c] >= gauche:
            gauche = vus[c] + 1   # on rétrécit pour exclure le doublon
        vus[c] = droite
        meilleur = max(meilleur, droite - gauche + 1)
    return meilleur

Le pointeur droite parcourt la chaîne une fois ; le pointeur gauche ne fait qu'avancer, jamais reculer. Chaque caractère est donc traité au plus deux fois : O(n). L'approche naïve, qui testerait chaque sous-chaîne, serait en O(n²) voire O(n³).

Voici la même logique en TypeScript pour le plus petit sous-tableau dont la somme atteint une cible :

typescriptfunction plusPetitSousTableau(arr: number[], cible: number): number {
  let gauche = 0, somme = 0, meilleur = Infinity;
  for (let droite = 0; droite < arr.length; droite++) {
    somme += arr[droite];           // on étend à droite
    while (somme >= cible) {        // contrainte atteinte : on rétrécit
      meilleur = Math.min(meilleur, droite - gauche + 1);
      somme -= arr[gauche++];
    }
  }
  return meilleur === Infinity ? 0 : meilleur;
}

Reconnaître le pattern

La fenêtre glissante s'applique quand un problème combine ces traits :

• on cherche quelque chose sur un sous-tableau ou une sous-chaîne contigus (pas n'importe quel sous-ensemble) ;
• le mot-clé est « le plus long », « le plus court », « la somme maximale », « contenant au plus K… » ;
• on peut mettre à jour le résultat de la fenêtre de façon incrémentale quand elle bouge (ajouter/retirer un élément).

Le piège à éviter : la fenêtre glissante ne marche pas si le problème autorise des éléments non contigus, ou si retirer un élément ne se calcule pas simplement. Dans ces cas, il faut un autre outil.

L'article suivant traite le dernier pattern de la série, complémentaire de la fenêtre glissante quand on a beaucoup de requêtes de somme à servir : les sommes préfixes.

Sources

• Laakmann McDowell, G. (2015). Cracking the Coding Interview (6th ed.). CareerCup.
• Halim, S., & Halim, F. (2013). Competitive Programming 3, Section 3.2. Lulu.
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre sur les techniques de conception. MIT Press.