Monoton stack: ökande eller minskande
Upprätthåll en ökande eller minskande stack för att effektivt besvara frågor om nästa större respektive föregående mindre element på O(n).
Monoton stack: ökande eller minskande är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 1 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad är en monoton stack
En monoton stack är en stack som bevarar en sorterad ordning bland sina element, antingen alltid stigande från botten till toppen eller alltid fallande. Innan ett nytt element läggs på stacken tar vi bort alla element som bryter mot den monotona invarianten. Denna begränsade struktur möjliggör O(n)-lösningar på problem som annars skulle kräva nästlade loopar med O(n²).
Den viktiga insikten är att varje element läggs på och tas bort från stacken högst en gång, så det totala antalet operationer under genomgången av hela arrayen är O(n), inte O(n²). I samma ögonblick som vi tar bort ett element har vi hittat svaret som det väntade på.
# 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]Next Greater Element I
Problemet Next Greater Element går ut på att för varje element hitta det första elementet till höger som är större. En brute-force-metod med två nästlade loopar och O(n²) är för långsam. Med en monoton minskande stack löser vi problemet på O(n).
Behandla elementen från vänster till höger. Innan element i läggs på stacken tar du bort alla element från stacken som är mindre än nums[i] — nums[i] är nästa större element för alla dessa. När alla element har behandlats saknar de objekt som finns kvar på stacken ett större element till höger (svar = -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]Nästa större element: spåra algoritmen
Låt oss spåra [2, 1, 2, 4, 3] steg för steg. Vi upprätthåller en avtagande stack med index vars nästa större element ännu inte har hittats.
- i=0, val=2: stacken är tom, 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 är nums[0]=2 inte < 2, 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]
- Slut: stacken [3,4] har 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])Föregående mindre element
Monotona stackar kan också besvara frågor om föregående mindre element (PSE): för varje element det närmaste elementet till vänster som är mindre. I stället för att poppa vid ett större element poppar vi vid ett större eller lika stort element och registrerar stacktoppen som PSE innan vi pushar.
Riktningen ändras: vi bearbetar fortfarande från vänster till höger, men i stället för att besvara frågor när vi poppar besvarar vi dem precis innan vi pushar. Stacktoppen i det ögonblicket är det närmaste mindre elementet till vänster. Om stacken är tom finns det inget mindre element till vänster (svaret = -1 eller en sentinel).
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]Daily Temperatures: vänta på varmare dagar
Problemet Daily Temperatures (LeetCode 739): givet dagliga temperaturer ska ni returnera en array där varje element anger antalet dagar tills temperaturen blir varmare. Detta är exakt mönstret för nästa större element, men i stället för det större värdet vill vi ha antalet dagar (skillnaden mellan indexen).
Använd en monoton avtagande stack med index. När vi hittar en varmare temperatur vid index i poppar vi alla index j från stacken där temps[j] < temps[i] och sätter result[j] = i - j. Kvarvarande index har ingen framtida varmare 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]Ökande eller avtagande stack: när ska de användas
Det är avgörande att välja rätt stackriktning:
- Monoton avtagande stack (poppa när current > top): besvarar frågor om nästa större element och föregående större element. Används i daily-temperatures, largest-rectangle och trap-rain-water.
- Monoton ökande stack (poppa när current < top): besvarar frågor om nästa mindre element och föregående mindre element. Används för att hitta aktiekursspannet och antalet synliga personer i en kö.
Kom ihåg: elementet som orsakar en pop är svaret på frågan för det poppade elementet — antingen nästa större eller nästa mindre element, beroende på vilken invariant ni upprätthåller.
# 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)Cirkulärt nästa större element
Next Greater Element II (LeetCode 503): givet en cirkulär array (med omslag) ska ni hitta nästa större element. Tricket är att bearbeta arrayen två gånger genom att dubbla indexen: iterera från 0 till 2n-1 och använda index % n för att gå runt. Vi pushar bara index från 0 till n-1 (första genomgången) så att vi inte räknar samma element två gånger.
Alternativt kan ni bearbeta arrayen i den andra genomgången utan att pusha nya index — endast poppa. Detta hanterar den cirkulära uppslagningen korrekt utan att faktiskt duplicera arrayen, samtidigt som utrymmet hålls till 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]Stock Span-problemet
Problemet Stock Span: givet dagliga aktiekurser ska ni beräkna spannet för varje dag — antalet sammanhängande föregående dagar med ett pris som är mindre än eller lika med dagens pris. Detta är problemet med föregående större element i förklädnad: spannet är avståndet från idag tillbaka till den närmaste dagen med ett strikt högre pris.
Använd en monoton avtagande stack. När dag i bearbetas poppar ni alla dagar med pris ≤ current. Spannet är i - stack[-1] om stacken inte är tom, eller i + 1 om den är tom (priset är det högsta hittills). Pusha sedan 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 = 6Monoton stack för synliga personer i en kö
Problemet Number of Visible People in a Queue: personer står i en kö, och varje person har en längd. Person i kan se person j (j > i) om alla personer mellan dem är kortare än båda. Detta använder en monoton avtagande stack.
Bearbeta kön från höger till vänster. Upprätthåll en avtagande stack med längder. För varje person räknar ni hur många personer som kan ses: poppa alla kortare personer (synliga men därefter blockerade), plus 1 om stacken fortfarande inte är tom (den första längre personen syns också). Detta ger totalt O(n), eftersom varje person pushas och poppas högst en gång.
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)-garantin: varför varje element pushas och poppas högst en gång
Tidskomplexiteten O(n) för algoritmer med monotona stackar bygger på ett enkelt amortiseringsargument: varje element pushas på stacken exakt en gång och poppas högst en gång. Inget element kan pushas eller poppas mer än en gång. Därför är det totala antalet push- och pop-operationer i hela loopen högst 2n, vilket ger O(n) totalt arbete trots att den nästlade while-loopen kan se ut att innebära O(n²).
Denna amortiserade analys är viktig att kunna förklara under tekniska intervjuer. While-loopen körs inte n gånger per iteration — den körs bara så länge det behövs för att poppa element som väntade, och dessa element är borta för alltid när de väl har poppats.
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 <= 2nKänna igen problem med monotona stackar
Ett problem behöver sannolikt en monoton stack om det frågar efter närmaste större eller mindre element, aktiekursspan, synliga element i en rad eller histogrambaserade areor. Leta efter dessa nyckelord och mönster: varje element behöver svaret från det närmaste relevanta elementet i en riktning (åt vänster eller höger).
Om en brute-force-lösning söker åt vänster eller höger från varje element (O(n²)), ersätter ni sökningen med en monoton stack. Stacken ”minns” kandidatsvar, sorterar bort irrelevanta kandidater och poppar fram rätt svar precis när det behövs.
# 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()Snabbkontroll
Testa er förståelse av begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning av lektionen
I den här lektionen lärde ni er att en monoton stack upprätthåller en ökande eller avtagande ordning genom att poppa element som bryter mot invarianten innan de pushas, att en avtagande stack besvarar frågor om nästa eller föregående större element, medan en ökande stack besvarar frågor om nästa eller föregående mindre element, samt att varje element pushas och poppas högst en gång, vilket ger O(n) totalt — inte O(n²). Härnäst använder vi den monotona stacken för att hitta den största rektangeln i ett histogram.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Monoton stack: ökande eller minskande” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Monoton stack: ökande eller minskande”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Monoton stack: ökande eller minskande”?
Upprätthåll en ökande eller minskande stack för att effektivt besvara frågor om nästa större respektive föregående mindre element på O(n). Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”Monoton stack: ökande eller minskande”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Monoton stack: ökande eller minskande
- Största rektangeln i ett histogram
- Maximalt värde i ett glidande fönster med monoton deque
- Trapping Rain Water: stack och två pekare