Schéma de la pile monotone
Appliquez la pile monotone pour résoudre daily-temperatures, largest-rectangle-in-histogram et next-greater-element en O(n).
Schéma de la pile monotone est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 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.
Qu’est-ce qu’une pile monotone
Une pile monotone est une pile qui maintient un invariant de tri entre ses éléments. Une pile monotone croissante contient des éléments croissants du bas vers le haut ; une pile monotone décroissante contient des éléments décroissants du bas vers le haut. Lorsqu’un nouvel élément viole l’invariant, les éléments sont dépilés jusqu’à ce que l’invariant soit rétabli, puis le nouvel élément est empilé.
Ce mécanisme simple permet de répondre en O(n) aux requêtes concernant l’élément supérieur ou inférieur le plus proche, qui nécessiteraient naïvement des boucles imbriquées en O(n²).
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)Élément supérieur suivant (LeetCode 496)
Pour chaque élément, trouvez le premier élément strictement supérieur situé à sa droite. Une approche par force brute en O(n²) parcourt les éléments vers la droite depuis chaque position. L’approche par pile monotone consiste à conserver une pile décroissante d’indices. Lorsqu’un élément plus grand est rencontré, dépilez tous les indices correspondant à des éléments plus petits : leur « élément supérieur suivant » est l’élément courant. Les indices restants n’ont aucun élément supérieur suivant ; leur réponse est -1.
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]Élément supérieur suivant dans un tableau circulaire
LeetCode 503 « Élément supérieur suivant II » : le même problème, mais le tableau est considéré comme circulaire. Après avoir atteint la fin, revenez au début et poursuivez la recherche. L’astuce consiste à parcourir le tableau deux fois (indices 0 à 2n-1) et à utiliser i % n pour accéder au tableau d’origine. N’empilez que les indices compris dans l’intervalle [0, n-1] afin d’éviter les traitements en double.
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Températures quotidiennes : solution complète
Retour sur LeetCode 739 : pour chaque jour, combien de jours faut-il attendre avant une température plus élevée ? La pile monotone contient les indices des jours dont les températures sont dans un ordre décroissant. Lorsqu’un jour plus chaud i est trouvé, dépilez tous les indices j des jours plus froids et enregistrez result[j] = i - j. Les jours restants dans la pile n’ont jamais trouvé de jour plus chaud ; leur résultat reste donc égal à 0.
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]Élément inférieur précédent
La requête concernant l’« élément inférieur précédent » demande : pour chaque élément, quelle est la valeur inférieure la plus proche à sa gauche ? Utilisez une pile monotone croissante en parcourant les éléments de gauche à droite. Avant d’empiler l’indice i, le sommet de la pile est l’élément inférieur précédent, car tous les éléments supérieurs à l’élément courant ont déjà été dépilés lors des insertions précédentes.
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]Plus grand rectangle dans un histogramme
LeetCode 84 « Plus grand rectangle dans un histogramme » : utilisez une pile monotone croissante d’indices. Pour chaque barre, dépilez toutes les barres plus hautes que la barre courante. Pour chaque barre dépilée h, sa limite droite est l’indice courant i et sa limite gauche est le nouveau sommet de la pile + 1 (ou 0 si la pile est vide). Aire = h × (droite - gauche). Ajoutez une sentinelle de hauteur 0 pour forcer le dépilement de toutes les barres restantes à la fin.
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1Rectangle maximal (LeetCode 85)
LeetCode 85 « Rectangle maximal » étend le problème de l’histogramme à une matrice binaire en 2D. Pour chaque ligne, calculez les hauteurs cumulées des barres : si matrix[row][col] == '1', la hauteur correspond au nombre de 1 consécutifs situés au-dessus de cette cellule et dans celle-ci. Appliquez ensuite l’algorithme du « plus grand rectangle dans un histogramme » au tableau des hauteurs de chaque ligne. Complexité temporelle : O(m × n) pour une matrice m×n.
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6Piéger l’eau de pluie : approche par pile
LeetCode 42 « Piéger l’eau de pluie » avec une pile : maintenez une pile décroissante d’indices. Lorsqu’une barre plus haute est rencontrée, un creux se forme. Dépilez le fond du creux, puis calculez la largeur d’eau comme (indice courant - sommet de la pile - 1) et la hauteur comme (minimum entre la barre courante et la barre au sommet de la nouvelle pile - hauteur du creux). Additionnez toutes les contributions. Complexité temporelle : O(n), espace utilisé : O(n).
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9Reconnaître les problèmes de pile monotone
Voici les signes indiquant qu’une pile monotone est l’outil adapté : le problème demande l’élément supérieur ou inférieur suivant ou précédent, la réponse pour chaque élément dépend d’éléments situés dans une direction précise, ou une solution naïve en O(n²) consiste à parcourir les éléments vers la gauche ou la droite pour chaque élément. La pile conserve les candidats susceptibles de devenir les réponses pour les éléments suivants et les élimine dès qu’un meilleur candidat apparaît.
Décidez toujours à l’avance : pile croissante (pour les éléments inférieurs suivants ou précédents) ou décroissante (pour les éléments supérieurs suivants ou précédents), ainsi que la direction du parcours.
Analyse amortie en O(n)
Les algorithmes de pile monotone semblent d’abord être en O(n log n) ou O(n²) à cause de la boucle conditionnelle à l’intérieur de la boucle d’itération. Mais chaque élément est empilé au plus une fois et dépilé au plus une fois. Le nombre total d’opérations d’empilement est n, et le nombre total d’opérations de dépilement est également au plus n. Ainsi, sur l’ensemble des itérations, le travail total correspond à 2n opérations, soit O(n) amorti et non O(n²).
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nRésumé : choix des invariants de pile monotone
Choisissez la direction de la pile en fonction de la requête. Pour l’élément supérieur suivant, utilisez une pile décroissante et dépilez lorsque l’élément courant est plus grand. Pour l’élément inférieur suivant, utilisez une pile croissante et dépilez lorsque l’élément courant est plus petit. Pour le plus grand rectangle, utilisez une pile croissante et dépilez lorsqu’une barre plus courte apparaît. Pour le maximum d’une fenêtre glissante, utilisez une file à double extrémité décroissante et retirez les éléments des deux extrémités.
Écrire l’invariant dans un commentaire avant de coder clarifie la logique et accélère la recherche des erreurs.
Vérification rapide
Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris qu’une pile monotone maintient un invariant de tri en dépilant les éléments qui le violent avant d’empiler le nouvel élément, que les piles décroissantes répondent aux requêtes concernant l’élément supérieur suivant, tandis que les piles croissantes répondent à celles concernant l’élément inférieur suivant, et que la complexité temporelle totale est O(n) amorti, car chaque élément est empilé et dépilé au plus une fois. Nous allons maintenant implémenter des files à l’aide de piles et des piles à l’aide de files.
Questions Fréquemment Posées
La leçon « Schéma de la pile monotone » est-elle gratuite ?
Oui — le texte complet de « Schéma de la pile monotone » 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 « Schéma de la pile monotone » ?
Appliquez la pile monotone pour résoudre daily-temperatures, largest-rectangle-in-histogram et next-greater-element en O(n). 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 3 sur 4.
Combien de temps prend la leçon « Schéma de la pile monotone » ?
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
- Implémentation et applications d’une pile
- Implémentation d’une file et d’une deque
- Schéma de la pile monotone
- Simulation réciproque d’une pile et d’une file