Monotone stack: oplopend versus aflopend
Houd een oplopende of aflopende stack bij om queries naar het volgende grotere en vorige kleinere element efficiënt te beantwoorden in O(n).
Monotone stack: oplopend versus aflopend is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat is een monotone stack?
Een monotone stack is een stack die de elementen in gesorteerde volgorde houdt, dus altijd oplopend van onder naar boven of altijd aflopend. Voordat je een nieuw element op de stack plaatst, verwijder je alle elementen die de monotone invariant schenden. Dankzij deze beperkte structuur kun je problemen in O(n) oplossen waarvoor anders geneste lussen met O(n²) nodig zouden zijn.
Het belangrijkste inzicht: elk element wordt hoogstens één keer op de stack geplaatst en één keer verwijderd, zodat het totale aantal bewerkingen tijdens het doorlopen van de hele array O(n) is — niet O(n²). Op het moment dat je een element van de stack verwijdert, heb je het antwoord gevonden waarop het wachtte.
# 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]Eerstvolgend groter element I
Bij het probleem Eerstvolgend groter element zoek je voor elk element het eerste element rechts ervan dat groter is. Een uitputtende dubbele lus van O(n²) is te traag. Met een monotone aflopende stack lossen we dit op in O(n).
Verwerk de elementen van links naar rechts. Voordat je element i op de stack plaatst, verwijder je alle elementen van de stack die kleiner zijn dan nums[i] — nums[i] is het eerstvolgend grotere element voor elk van die elementen. Na verwerking van alle elementen hebben de resterende elementen op de stack geen groter element rechts van zich staan (answer = -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]Volgend groter element: het algoritme stap voor stap volgen
We volgen [2, 1, 2, 4, 3] stap voor stap. We houden een afnemende stapel met indexen bij waarvoor het volgende grotere element nog niet is gevonden.
- i=0, val=2: stack is leeg, push 0. Stack: [0]
- i=1, val=1: 1 < nums[0]=2, push 1. Stack: [0,1]
- i=2, val=2: pop 1 (nums[1]=1 < 2), result[1]=2; nu is nums[0]=2 niet < 2, dus push 2. Stack: [0,2]
- i=3, val=4: pop 2 (result[2]=4), pop 0 (result[0]=4), push 3. Stack: [3]
- i=4, val=3: 3 < nums[3]=4, push 4. Stack: [3,4]
- Einde: stack [3,4] heeft result=-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])Vorig kleiner element
Monotone stapels kunnen ook vragen over het vorige kleinere element (PSE) beantwoorden: voor elk element het dichtstbijzijnde element links ervan dat kleiner is. In plaats van bij een groter element elementen van de stapel te halen, doen we dat bij een groter of gelijk element en leggen we de top van de stapel als het PSE vast voordat we het huidige element op de stapel zetten.
De richting verandert: we verwerken de elementen nog steeds van links naar rechts, maar in plaats van vragen te beantwoorden wanneer we elementen van de stapel halen, beantwoorden we ze vlak vóór we een element op de stapel zetten. De top van de stapel is op dat moment het dichtstbijzijnde kleinere element links ervan. Als de stapel leeg is, is er geen kleiner element links (antwoord = -1 of een wachtwaarde).
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]Dagelijkse temperaturen: wachten op warmere dagen
Het probleem Dagelijkse temperaturen (LeetCode 739): gegeven dagelijkse temperaturen retourneer je een array waarin elk element het aantal dagen tot een warmere temperatuur bevat. Dit is precies het patroon van het volgende grotere element, maar in plaats van de grotere waarde willen we het aantal dagen (het indexverschil).
Gebruik een monotone afnemende stapel met indexen. Wanneer we op index i een warmere temperatuur vinden, halen we alle indexen j van de stapel waarvoor temps[j] < temps[i] en stellen we result[j] = i - j in. De overgebleven indexen hebben geen toekomstige warmere dag (result = 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]Toenemende versus afnemende stapel: wanneer gebruik je welke
De juiste richting voor de stapel kiezen is cruciaal:
- Monotone afnemende stapel (elementen van de stapel halen wanneer huidig > top): beantwoordt vragen over het volgende grotere element en het vorige grotere element. Gebruikt bij dagelijkse temperaturen, de grootste rechthoek en het opvangen van regenwater.
- Monotone toenemende stapel (elementen van de stapel halen wanneer huidig < top): beantwoordt vragen over het volgende kleinere element en het vorige kleinere element. Gebruikt bij het bepalen van het bereik van aandelenkoersen en het aantal zichtbare mensen in een rij.
Onthoud: het element dat ervoor zorgt dat een element van de stapel wordt gehaald, is het antwoord op de vraag van dat verwijderde element — het volgende grotere of volgende kleinere element, afhankelijk van welke invariant je handhaaft.
# 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)Circulair volgend groter element
Volgend groter element II (LeetCode 503): gegeven een circulaire array (met terugloop) zoek je het volgende grotere element. De truc is om de array twee keer te verwerken door de indexen te verdubbelen: loop van 0 tot 2n-1 en gebruik index % n om terug te lopen. We zetten alleen indexen van 0 tot n-1 op de stapel (de eerste doorgang), zodat we niets dubbel tellen.
Je kunt de array in de tweede doorgang ook verwerken zonder nieuwe indexen op de stapel te zetten — je haalt dan alleen elementen van de stapel. Zo wordt het vooruitkijken in de circulaire array correct afgehandeld zonder de array daadwerkelijk te dupliceren, terwijl de ruimtecomplexiteit O(n) blijft.
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]Probleem van de aandelenkoersspanwijdte
Het probleem van de aandelenkoersspanwijdte: gegeven dagelijkse aandelenkoersen bereken je de spanwijdte van elke dag — het aantal opeenvolgende voorafgaande dagen waarop de koers kleiner dan of gelijk aan de koers van vandaag was. Dit is in feite het probleem van het vorige grotere element: de spanwijdte is de afstand van vandaag terug naar de dichtstbijzijnde dag met een strikt hogere koers.
Gebruik een monotone afnemende stapel. Wanneer je dag i verwerkt, haal je alle dagen met een koers ≤ de huidige koers van de stapel. De spanwijdte is i - stack[-1] als de stapel niet leeg is, of i + 1 als hij leeg is (de koers is tot nu toe maximaal). Zet daarna i op de stapel.
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 = 6Monotone stapel voor zichtbare mensen in een rij
Het probleem Aantal zichtbare mensen in een rij: mensen staan in een rij en hebben elk een bepaalde lengte. Persoon i kan persoon j zien (j > i) als alle mensen tussen hen korter zijn dan beiden. Hiervoor gebruik je een monotone afnemende stapel.
Verwerk de mensen van rechts naar links. Houd een afnemende stapel met lengtes bij. Tel voor elke persoon hoeveel mensen die kan zien: haal alle kortere mensen van de stapel (zichtbaar, maar daarna geblokkeerd), plus 1 als de stapel daarna niet leeg is (de eerste langere persoon is ook zichtbaar). Dit kost in totaal O(n), omdat elke persoon hoogstens één keer op de stapel wordt gezet en er weer van wordt gehaald.
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]O(n)-garantie: waarom elk element hoogstens één keer op de stapel wordt gezet en er weer van wordt gehaald
De tijdsgarantie O(n) van algoritmen met een monotone stapel komt voort uit een eenvoudig amortisatieargument: elk element wordt precies één keer op de stapel gezet en hoogstens één keer verwijderd. Geen enkel element kan vaker dan één keer op de stapel worden gezet of ervan worden gehaald. Daarom zijn er in de hele lus hoogstens 2n bewerkingen voor het toevoegen en verwijderen, wat in totaal O(n) werk oplevert, ook al lijkt de geneste while-lus O(n²) te suggereren.
Deze amortisatieanalyse is belangrijk om tijdens technische sollicitatiegesprekken duidelijk uit te leggen. De while-lus wordt niet bij elke iteratie n keer uitgevoerd — hij wordt alleen zo vaak uitgevoerd als nodig is om elementen te verwijderen die op hun beurt wachtten, en die elementen komen nooit meer terug nadat ze zijn verwijderd.
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 <= 2nMonotone-stapelproblemen herkennen
Een probleem heeft waarschijnlijk een monotone stapel nodig als het vraagt naar het dichtstbijzijnde grotere of kleinere element, de spanwijdte van koersen, zichtbare elementen in een rij of oppervlakken op basis van histogrammen. Let op deze trefwoorden en patronen: elk element heeft het antwoord nodig van het dichtstbijzijnde relevante element in één richting (links of rechts).
Als een uitputtende oplossing vanaf elk element naar links of rechts scant (O(n²)), vervang je die scan door een monotone stapel. De stapel onthoudt kandidaatantwoorden, verwerpt irrelevante kandidaten en haalt het juiste antwoord precies op het moment van de stapel wanneer het nodig is.
# 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()Snelle controle
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep die in deze les aan bod kwamen.
Samenvatting van de les
In deze les heb je geleerd: een monotone stapel handhaaft een oplopende of aflopende volgorde door elementen die de invariant schenden te verwijderen voordat een element op de stapel wordt gezet, een afnemende stapel beantwoordt vragen over het volgende of vorige grotere element, terwijl een toenemende stapel vragen over het volgende of vorige kleinere element beantwoordt, en elk element wordt hoogstens één keer op de stapel gezet en ervan verwijderd, wat in totaal O(n) tijd oplevert — niet O(n²). Vervolgens passen we de monotone stapel toe om de grootste rechthoek in een histogram te vinden.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Monotone stack: oplopend versus aflopend” gratis?
Ja — de volledige tekst van “Monotone stack: oplopend versus aflopend” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Monotone stack: oplopend versus aflopend”?
Houd een oplopende of aflopende stack bij om queries naar het volgende grotere en vorige kleinere element efficiënt te beantwoorden in O(n). Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Monotone stack: oplopend versus aflopend”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Monotone stack: oplopend versus aflopend
- Grootste rechthoek in een histogram
- Maximum in een sliding window met een monotone deque
- Trapping Rain Water: stack en two-pointer