Pile monotone : élément suivant plus grand
Répondre aux requêtes d’étendue en un seul parcours
Pile monotone : élément suivant plus grand est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Le problème du prochain élément supérieur
Pour chaque nombre, vous cherchez la première valeur plus grande située à sa droite. La force brute coûte O(n carré), mais une pile monotone résout le problème en un seul parcours.
Ce que signifie monotone
Une pile monotone conserve ses valeurs dans un ordre trié, ici décroissant, de sorte que dès que cet ordre est rompu, vous savez qu’une réponse a été trouvée.
Mémoriser les indices, pas les valeurs
Empilez les indices plutôt que les nombres eux-mêmes. Vous saurez ainsi exactement quelle position remplir lorsqu’un élément plus grand apparaît.
stack = []
ans = [-1] * len(nums)Parcourir de gauche à droite
Parcourez le tableau une seule fois. À chaque indice, vous retirez les éléments dont la réponse est connue ou vous empilez l’indice actuel pour plus tard.
for i in range(len(nums)):Retirer les plus petits
Tant que la valeur actuelle dépasse la valeur située à l’indice au sommet, cet élément a enfin trouvé son prochain élément supérieur.
while stack and nums[i] > nums[stack[-1]]:Enregistrer la réponse
Retirez l’indice au sommet et définissez sa réponse comme étant la valeur actuelle. Chaque indice est traité exactement une fois, ce qui maintient un temps de calcul linéaire.
j = stack.pop()
ans[j] = nums[i]Empiler et continuer
Après avoir traité tous les éléments plus petits, empilez l’indice actuel afin qu’il attende son propre élément supérieur futur.
stack.append(i)Les éléments restants n’ont pas de réponse
Les indices encore présents dans la pile à la fin n’ont jamais rencontré de valeur plus grande. Ils conservent leur valeur par défaut, -1, ce qui signifie qu’aucun élément n’existe.
Pourquoi le temps est en O(n)
Chaque indice est empilé une fois et retiré une fois. Même avec la boucle while interne, le travail total reste linéaire sur l’ensemble du parcours.
Inverser pour le prochain élément inférieur
Vous avez plutôt besoin du prochain élément inférieur ? Maintenez la pile dans un ordre croissant en inversant la comparaison de supérieur à inférieur.
while stack and nums[i] < nums[stack[-1]]:Un modèle, pas une astuce
Les requêtes d’étendue, les cours boursiers et les aires d’histogrammes réutilisent tous cette idée. La pile monotone est un modèle essentiel des concours qui mérite d’être mémorisé.
Vérification rapide
Vous résolvez le problème du prochain élément supérieur avec une pile monotone. Pourquoi le temps total est-il linéaire ?
Récapitulatif : un parcours, de nombreuses réponses
Vous avez utilisé une pile monotone décroissante d’indices pour trouver les éléments supérieurs suivants en O(n). Ce modèle permet de résoudre de nombreux problèmes d’étendue. 🚀
Questions Fréquemment Posées
La leçon « Pile monotone : élément suivant plus grand » est-elle gratuite ?
Oui — le texte complet de « Pile monotone : élément suivant plus grand » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Pile monotone : élément suivant plus grand » ?
Répondre aux requêtes d’étendue en un seul parcours Tu pratiques Coding Interview Prep 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep 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 2 sur 4.
Combien de temps prend la leçon « Pile monotone : élément suivant plus grand » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep 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