Motif 3 — Fenêtre glissante

L'idée, en une ligne

Gardez une plage mobile sur votre liste, et réutilisez la dernière réponse au lieu de tout recompter de zéro. C'est le motif fenêtre glissante, et il transforme une double boucle lente en une seule passe.

Comment le repérer

La tâche demande la plus longue, la plus courte, la somme maximale, ou la meilleure séquence d'éléments côte à côte — une portion de la liste, pas un choix éparpillé. Ces mots la trahissent :

• fenêtre — une portée fixe que vous faites glisser
• consécutif — des éléments à la suite, sans trou
• sous-chaîne — une séquence de caractères, pas des lettres éparpillées

Deux variantes

Fenêtre fixe de taille k : additionnez les k premiers éléments, puis glissez en ajoutant l'élément qui entre et en soustrayant celui qui sort — window += arr[i] - arr[i-k] — en gardant la trace du meilleur vu.

Fenêtre variable : agrandissez l'extrémité droite pour laisser entrer plus, et quand une règle est brisée — un doublon, ou une somme au-dessus du budget — rétrécissez depuis la gauche jusqu'à ce que la règle tienne à nouveau. Un dict ou un set retient ce qui est actuellement à l'intérieur.

Voyez-le à l'œuvre

# Fixed window: most total requests in any 3-minute span
def max_window_sum(counts, k):
    window = sum(counts[:k])
    best = window
    for i in range(k, len(counts)):
        window += counts[i] - counts[i - k]   # add new, drop old
        best = max(best, window)
    return best

print(max_window_sum([2, 1, 5, 1, 3, 2], 3))  # 9  (5+1+3)

Lisez-le de haut en bas : additionnez les trois premiers, puis à chaque étape ajoutez la minute entrante et soustrayez la sortante. Vous ne ré-additionnez jamais toute la fenêtre — seulement les deux nombres qui ont changé.

# Variable window: longest run with no repeating character
def longest_unique(s):
    seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1   # shrink past the duplicate
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))            # 3  ('abc')

Avancé — le modèle mental

Toute l'accélération vient d'une habitude : au lieu de relire toute la fenêtre à chaque étape, vous ne comptez que l'unique élément qui entre et celui qui sort. C'est la différence entre vérifier chaque paire et faire un seul parcours — O(n) au lieu de O(n²).

Basé sur le tutoriel « Sliding Window Technique » de GeeksforGeeks