Pile monotone : croissante ou décroissante
Maintenez une pile croissante ou décroissante afin de répondre efficacement aux requêtes sur l’élément suivant plus grand et l’élément précédent plus petit en O(n).
Pile monotone : croissante ou décroissante est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 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 DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce qu'une pile monotone
Une pile monotone est une pile qui maintient ses éléments dans un ordre trié, soit toujours croissant du bas vers le haut, soit toujours décroissant. Avant d'empiler un nouvel élément, nous dépilons tous les éléments qui violent l'invariant de monotonie. Cette structure contrainte permet de résoudre en O(n) des problèmes qui nécessiteraient autrement des boucles imbriquées en O(n²).
L'idée essentielle est que chaque élément est empilé et dépilé au plus une fois. Ainsi, le nombre total d'opérations sur l'ensemble du parcours du tableau est O(n), et non O(n²). Au moment où nous dépilons un élément, nous avons trouvé the réponse qu'il attendait.
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]Premier élément supérieur suivant
Le problème du premier élément supérieur suivant consiste, pour chaque élément, à trouver le premier élément situé à sa droite qui lui est supérieur. Une double boucle par force brute en O(n²) est trop lente. Avec une pile monotone décroissante, nous résolvons ce problème en O(n).
Traitez les éléments de gauche à droite. Avant d'empiler l'élément i, dépilez tous les éléments de la pile qui sont inférieurs à nums[i] : nums[i] est the élément supérieur suivant de chacun d'eux. Une fois tous les éléments traités, ceux qui restent dans the pile n'ont aucun élément supérieur à leur droite (réponse = -1).
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]Élément supérieur suivant : suivre l’algorithme
Suivons [2, 1, 2, 4, 3] étape par étape. Nous maintenons une pile décroissante d’indices dont l’élément supérieur suivant n’a pas encore été trouvé.
- i=0, valeur=2 : pile vide, empiler 0. Pile : [0]
- i=1, valeur=1 : 1 < nombres[0]=2, empiler 1. Pile : [0,1]
- i=2, valeur=2 : pop 1 (nombres[1]=1 < 2), résultat[1]=2 ; maintenant nombres[0]=2 n’est pas < 2, empiler 2. Pile : [0,2]
- i=3, valeur=4 : pop 2 (résultat[2]=4), pop 0 (résultat[0]=4), empiler 3. Pile : [3]
- i=4, valeur=3 : 3 < nombres[3]=4, empiler 4. Pile : [3,4]
- Fin : pour les éléments de la pile [3,4], résultat=-1
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])Élément inférieur précédent
Les piles monotones permettent également de répondre aux requêtes concernant l’élément inférieur précédent : pour chaque élément, l’élément le plus proche à sa gauche qui lui est inférieur. Au lieu de dépiler lorsqu’un élément supérieur est rencontré, on dépile lorsqu’un élément supérieur ou égal est rencontré et on enregistre le sommet de la pile comme élément inférieur précédent avant d’empiler.
La manière de répondre change : nous parcourons toujours les éléments de gauche à droite, mais au lieu de répondre aux questions lors des dépilements, nous y répondons juste avant d’empiler. Le sommet de la pile à ce moment-là est l’élément inférieur le plus proche à gauche. Si la pile est vide, il n’y a aucun élément inférieur à gauche (la réponse vaut -1 ou une valeur sentinelle).
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]Températures quotidiennes : attendre les jours plus chauds
Le problème des températures quotidiennes (LeetCode 739) consiste, à partir des températures quotidiennes, à renvoyer un tableau dont chaque élément indique le nombre de jours à attendre avant une température plus élevée. Il s’agit exactement du motif de l’élément supérieur suivant, mais au lieu de la valeur supérieure, nous voulons le nombre de jours (la différence entre les indices).
Utilisez une pile décroissante monotone d’indices. Lorsque nous trouvons une température plus élevée à l’indice i, dépilez tous les indices j de la pile tels que temps[j] < temps[i] et définissez result[j] = i - j. Les indices restants n’ont aucun jour futur plus chaud (le résultat vaut 0).
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]Pile croissante ou décroissante : quand utiliser chacune
Choisir la bonne direction de la pile est essentiel :
- Pile décroissante monotone (dépiler lorsque l’élément courant > sommet) : répond aux requêtes concernant l’élément supérieur suivant et l’élément supérieur précédent. Utilisée pour les températures quotidiennes, le plus grand rectangle et la récupération de l’eau de pluie.
- Pile croissante monotone (dépiler lorsque l’élément courant < sommet) : répond aux requêtes concernant l’élément inférieur suivant et l’élément inférieur précédent. Utilisée pour calculer l’étendue des cours boursiers et le nombre de personnes visibles dans une file.
Souvenez-vous-en : l’élément qui provoque un dépilement est la réponse à la requête de l’élément dépilé — soit l’élément supérieur suivant, soit l’élément inférieur suivant, selon l’invariant que vous maintenez.
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)Élément supérieur suivant dans un tableau circulaire
Le problème du deuxième élément supérieur suivant (LeetCode 503) consiste, à partir d’un tableau circulaire (avec retour au début), à trouver l’élément supérieur suivant. L’astuce consiste à parcourir le tableau deux fois en doublant les indices : parcourez les indices de 0 à 2n-1, en utilisant index % n pour revenir au début. Nous n’empilons que les indices de 0 à n-1 (lors du premier parcours) afin de ne pas compter deux fois les mêmes éléments.
Vous pouvez également parcourir le tableau lors du deuxième passage sans empiler de nouveaux indices — uniquement en dépilant. Cela gère correctement la recherche circulaire vers l’avant sans dupliquer réellement le tableau, tout en conservant un espace mémoire en O(n).
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Problème de l’étendue des cours boursiers
Le problème de l’étendue des cours boursiers consiste, à partir des cours quotidiens d’une action, à calculer l’étendue de chaque jour — le nombre de jours précédents consécutifs dont le cours est inférieur ou égal à celui du jour présent. Il s’agit en réalité du problème de l’élément supérieur précédent : l’étendue est la distance entre le jour présent et le jour le plus proche dont le cours est strictement supérieur.
Utilisez une pile décroissante monotone. Lors du traitement du jour i, faites pop de tous les jours dont le cours est ≤ au cours actuel. L’étendue vaut i - stack[-1] si la pile n’est pas vide, ou i + 1 si elle est vide (le cours est le plus élevé jusqu’ici). Empilez ensuite i.
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6Pile monotone pour les personnes visibles dans une file
Le problème du nombre de personnes visibles dans une file consiste à considérer des personnes qui attendent dans une file, chacune ayant une taille. La personne i peut voir la personne j (j > i) si toutes les personnes situées entre elles sont plus petites qu’elles deux. Ce problème utilise une pile décroissante monotone.
Parcourez les personnes de droite à gauche. Maintenez une pile décroissante de tailles. Pour chaque personne, comptez combien de personnes elle peut voir : faites pop de toutes les personnes plus petites (visibles, mais masquées ensuite), puis ajoutez 1 si la pile n’est pas vide après cette opération (la première personne plus grande est également visible). La complexité globale est ainsi O(n), car chaque personne est empilée et dépilée au plus une fois.
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]Garantie en O(n) : pourquoi chaque élément est empilé et dépilé au plus une fois
La garantie de temps d’exécution O(n) des algorithmes à pile monotone repose sur un simple raisonnement d’analyse amortie : chaque élément est empilé exactement une fois et dépilé au plus une fois. Aucun élément ne peut être empilé ou dépilé plus d’une fois. Par conséquent, le nombre total d’opérations d’empilement et de dépilement dans toute la boucle est au plus égal à 2n, ce qui donne un travail total en O(n), même si la boucle imbriquée semble suggérer une complexité en O(n²).
Cette analyse amortie est importante à expliquer lors des entretiens techniques. La boucle de répétition ne s’exécute pas n fois à chaque itération : elle s’exécute seulement assez longtemps pour dépiler les éléments qui attendaient, et ces éléments sont définitivement retirés après leur dépilement.
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2nReconnaître les problèmes de pile monotone
Un problème nécessite probablement une pile monotone s’il demande l’élément supérieur ou inférieur le plus proche, l’étendue des cours, les éléments visibles dans une file ou des aires fondées sur un histogramme. Repérez ces mots-clés et ces motifs : chaque élément doit obtenir la réponse à partir de l’élément pertinent le plus proche dans une direction donnée (à gauche ou à droite).
Si une solution par force brute parcourt les éléments vers la gauche ou vers la droite à partir de chaque élément (O(n²)), remplacez ce parcours par une pile monotone. La pile « mémorise » les réponses candidates, élimine celles qui ne sont pas pertinentes et dépile la bonne réponse exactement au moment où elle est nécessaire.
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()Vérification rapide
Testez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation — abordés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris qu’une pile monotone maintient un ordre croissant ou décroissant en dépilant les éléments qui violent l’invariant avant de les empiler, qu’une pile décroissante répond aux requêtes concernant l’élément supérieur suivant ou précédent, tandis qu’une pile croissante répond à celles concernant l’élément inférieur suivant ou précédent, et que chaque élément est empilé et dépilé au plus une fois, ce qui donne un temps total en O(n), et non en O(n²). Ensuite, nous appliquerons la pile monotone pour trouver le plus grand rectangle dans un histogramme.
Questions Fréquemment Posées
La leçon « Pile monotone : croissante ou décroissante » est-elle gratuite ?
Oui — le texte complet de « Pile monotone : croissante ou décroissante » 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 DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Pile monotone : croissante ou décroissante » ?
Maintenez une pile croissante ou décroissante afin de répondre efficacement aux requêtes sur l’élément suivant plus grand et l’élément précédent plus petit en O(n). Tu pratiques DSA 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 DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA 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 1 sur 4.
Combien de temps prend la leçon « Pile monotone : croissante ou décroissante » ?
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 DSA Interview Prep ?
Oui. Chaque leçon DSA 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
- Pile monotone : croissante ou décroissante
- Plus grand rectangle dans un histogramme
- Maximum dans une fenêtre glissante avec une deque monotone
- Accumulation d’eau de pluie : pile et deux pointeurs