Maximum d’une fenêtre glissante avec une deque
Conserver les extrêmes de la fenêtre en O(n)
Maximum d’une fenêtre glissante avec une deque est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Le maximum d’une fenêtre glissante
Étant donné un tableau et une taille de fenêtre k, vous cherchez le maximum de chaque fenêtre lorsqu’elle glisse vers la droite. Le faire naïvement coûte O(n fois k).
Une promesse plus rapide
Avec une file à double extrémité monotone, vous pouvez obtenir la réponse pour chaque fenêtre en O(n) au total, en parcourant le tableau une seule fois.
Mémoriser à nouveau les indices
Conservez les indices dans la file à double extrémité, pas les valeurs. Les indices vous permettent de vérifier si l’élément à l’avant est sorti de la fenêtre actuelle.
from collections import deque
dq = deque()
res = []La maintenir décroissante
La file à double extrémité reste décroissante selon la valeur, de l’avant vers l’arrière, de sorte que l’indice à l’avant pointe toujours vers le maximum de la fenêtre.
Retirer les extrémités plus petites
Avant d’ajouter l’indice i, retirez les éléments à l’arrière tant que leurs valeurs sont plus petites, car ils ne pourront jamais être un maximum futur.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Ajouter le nouvel indice
Après avoir supprimé les extrémités moins pertinentes, ajoutez l’indice actuel. L’ordre de la file à double extrémité reste correct pour les étapes suivantes.
dq.append(i)Expulser l’avant obsolète
Si l’indice à l’avant sort de la fenêtre, retirez-le avec popleft. Une fenêtre de taille k commence à l’indice i moins k plus un.
if dq[0] <= i - k:
dq.popleft()Enregistrer chaque maximum
Une fois la première fenêtre complète formée à l’indice k moins un, l’élément à l’avant de la file contient la réponse pour chaque position suivante.
if i >= k - 1:
res.append(nums[dq[0]])Faire attention à l’ordre d’expulsion
Expulsez l’élément obsolète à l’avant avant de lire la réponse. Sinon, vous pourriez signaler un maximum qui a déjà quitté la fenêtre.
Pourquoi le temps reste linéaire
Chaque indice est ajouté et retiré au plus une fois. Le travail de la file à double extrémité est donc amorti à O(1) par étape et à O(n) au total.
Fenêtre minimale, même idée
Pour obtenir le minimum d’une fenêtre glissante, maintenez plutôt la file à double extrémité dans un ordre croissant. Il suffit d’inverser la comparaison lors de la suppression à l’arrière.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Vérification rapide
Dans le problème du maximum d’une fenêtre glissante, que contient l’avant de la file à double extrémité monotone ?
Récapitulatif : la file à double extrémité gagne sur les fenêtres
Vous avez conservé une file à double extrémité décroissante d’indices : supprimez les extrémités petites, expulsez l’avant obsolète et lisez l’avant pour obtenir le maximum de chaque fenêtre en O(n). 🏆
Questions Fréquemment Posées
La leçon « Maximum d’une fenêtre glissante avec une deque » est-elle gratuite ?
Oui — le texte complet de « Maximum d’une fenêtre glissante avec une deque » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Maximum d’une fenêtre glissante avec une deque » ?
Conserver les extrêmes de la fenêtre en O(n) Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Maximum d’une fenêtre glissante avec une deque » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Piles pour faire correspondre les parenthèses
- Pile monotone : élément suivant plus grand
- Files et collections.deque
- Maximum d’une fenêtre glissante avec une deque