Pile monotone : élément suivant plus grand

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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é.

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. 🚀