Monoton stak: Stigende eller faldende
Vedligehold en stigende eller faldende stak for effektivt at besvare forespørgsler om næste større element og forrige mindre element i O(n).
Monoton stak: Stigende eller faldende er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad er en monoton stak
En monoton stak er en stak, der bevarer en sorteret rækkefølge af sine elementer, enten altid stigende fra bund til top eller altid faldende. Før du lægger et nyt element på stakken, fjerner du alle elementer, der overtræder den monotone invariant. Denne begrænsede datastruktur gør O(n)-løsninger mulige på problemer, der ellers ville kræve O(n²)-indlejrede løkker.
Den centrale indsigt er, at hvert element højst lægges på stakken én gang og fjernes én gang, så det samlede antal operationer under gennemløbet af hele arrayet er O(n) — ikke O(n²). I det øjeblik vi fjerner et element, har vi fundet det svar, det ventede 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]Næste større element I
Problemet med det næste større element går ud på at finde det første større element til højre for hvert element. En direkte løsning med to indlejrede løkker i O(n²) er for langsom. Med en monoton faldende stak kan vi løse problemet i O(n).
Gennemløb elementerne fra venstre mod højre. Før du lægger element i på stakken, fjerner du alle elementer fra stakken, der er mindre end nums[i] — nums[i] er det næste større element for dem alle. Når alle elementer er behandlet, har de resterende elementer på stakken ikke noget større element til højre (svaret er -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æste større element: Gennemgang af algoritmen
Lad os gennemgå [2, 1, 2, 4, 3] trin for trin. Vi vedligeholder en aftagende stak af indekser, hvis næste større element endnu ikke er fundet.
- i=0, val=2: stakken er tom, læg 0 på stakken. Stak: [0]
- i=1, val=1: 1 < nums[0]=2, læg 1 på stakken. Stak: [0,1]
- i=2, val=2: fjern 1 (nums[1]=1 < 2), result[1]=2; nu er nums[0]=2 ikke < 2, læg 2 på stakken. Stak: [0,2]
- i=3, val=4: fjern 2 (result[2]=4), fjern 0 (result[0]=4), læg 3 på stakken. Stak: [3]
- i=4, val=3: 3 < nums[3]=4, læg 4 på stakken. Stak: [3,4]
- Slut: stak [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])Forrige mindre element
Monotone stakke kan også besvare forespørgsler om forrige mindre element (PSE): for hvert element det nærmeste element til venstre, der er mindre. I stedet for at fjerne elementer ved et større element fjerner vi dem ved et større-eller-lig-med-element og registrerer staktoppen som PSE, før vi lægger elementet på stakken.
Retningen ændres: Vi gennemløber stadig fra venstre mod højre, men i stedet for at besvare spørgsmål, når vi fjerner elementer, besvarer vi dem lige før, vi lægger et element på stakken. Staktoppen på det tidspunkt er det nærmeste mindre element til venstre. Hvis stakken er tom, er der ikke noget mindre element til venstre (svaret = -1 eller en sentinelværdi).
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]Daglige temperaturer: Ventetid på varmere dage
Problemet Daglige temperaturer (LeetCode 739): Givet daglige temperaturer skal du returnere et array, hvor hvert element er antallet af dage, der går, før temperaturen bliver varmere. Dette er præcis mønsteret for næste større element, men i stedet for den større værdi ønsker vi antallet af dage (forskel mellem indekserne).
Brug en monotonisk aftagende stak af indekser. Når vi finder en varmere temperatur ved indeks i, fjerner vi alle indekser j fra stakken, hvor temps[j] < temps[i], og sætter result[j] = i - j. De resterende indekser har ingen varmere dag fremover (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]Stigende eller aftagende stak: Hvornår skal du bruge hvad
Det er afgørende at vælge den rigtige stakretning:
- Monotonisk aftagende stak (fjern et element, når det aktuelle element > staktoppen): bruges til forespørgsler om næste større element og forrige større element. Bruges i problemerne om daglige temperaturer, største rektangel og opsamling af regnvand.
- Monotonisk stigende stak (fjern et element, når det aktuelle element < staktoppen): bruges til forespørgsler om næste mindre element og forrige mindre element. Bruges til at finde aktiekursernes spænd og antallet af synlige personer i en kø.
Husk: Det element, der får et element til at blive fjernet, er svaret på forespørgslen for det fjernede element — enten det næste større eller det næste mindre element, afhængigt af hvilken invariant du opretholder.
# 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æste større element
Næste større element II (LeetCode 503): Givet et cirkulært array (der går rundt), skal du finde det næste større element. Fidusen er at gennemløbe arrayet to gange ved at bruge indekserne to gange: gennemløb fra 0 til 2n-1, og brug index % n til at gå rundt. Vi lægger kun indekser fra 0 til n-1 på stakken (første gennemløb), så vi ikke tæller elementerne dobbelt.
Alternativt kan du gennemløbe arrayet i det andet gennemløb uden at lægge nye indekser på stakken — kun fjerne elementer. Det håndterer korrekt, at vi skal kigge fremad i det cirkulære array, uden faktisk at kopiere arrayet, og holder pladsforbruget på 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]Problemet om aktiespænd
Aktiespænd-problemet: Givet daglige aktiekurser skal du beregne spændet for hver dag — antallet af sammenhængende foregående dage med en pris, der er mindre end eller lig med dagens pris. Dette er i virkeligheden problemet om det forrige større element: Spændet er afstanden fra i dag tilbage til den nærmeste dag med en strengt højere pris.
Brug en monotonisk aftagende stak. Når dag i behandles, fjernes alle dage med en pris ≤ den aktuelle pris. Spændet er i - stack[-1], hvis stakken ikke er tom, eller i + 1, hvis den er tom (prisen er den højeste hidtil). Læg derefter i på stakken.
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 stak til synlige personer i en kø
Problemet Antallet af synlige personer i en kø: Personer står i en kø, og hver person har en højde. Person i kan se person j (j > i), hvis alle personer mellem dem er lavere end dem begge. Dette bruger en monotonisk aftagende stak.
Gennemløb fra højre mod venstre. Vedligehold en aftagende stak af højder. For hver person tæller du, hvor mange personer vedkommende kan se: Fjern alle lavere personer (de er synlige, men bliver derefter blokeret), og læg 1 til, hvis stakken ikke er tom bagefter (den første højere person er også synlig). Det giver samlet O(n), fordi hver person højst lægges på stakken og fjernes fra den én gang.
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)-garanti: Hvorfor hvert element højst lægges på og fjernes fra stakken én gang
O(n)-tidskompleksiteten for algoritmer med monotone stakke skyldes et simpelt amortiseringsargument: Hvert element lægges præcis én gang på stakken og fjernes højst én gang. Intet element kan lægges på eller fjernes mere end én gang. Derfor er det samlede antal operationer med at lægge på og fjerne elementer i hele løkken højst 2n, hvilket giver O(n) samlet arbejde, selv om den indlejrede while-løkke kan se ud til at antyde O(n²).
Denne amortiserede analyse er vigtig at kunne forklare ved interviews. While-løkken kører ikke n gange pr. iteration — den kører kun længe nok til at fjerne de elementer, der ventede, og de elementer er væk for altid, når de først er fjernet.
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 <= 2nGenkend problemer med monotone stakke
Et problem har sandsynligvis brug for en monoton stak, hvis det spørger efter det nærmeste større eller mindre element, prisers spænd, synlige elementer på en række eller histogrambaserede arealer. Se efter disse nøgleord og mønstre: Hvert element skal have svaret fra det nærmeste relevante element i én retning (mod venstre eller højre).
Hvis en løsning med udtømmende søgning gennemgår elementerne mod venstre eller højre fra hvert element (O(n²)), kan du erstatte gennemgangen med en monoton stak. Stakken "husker" kandidatsvar, kasserer irrelevante kandidater og fjerner det rigtige svar præcis på det tidspunkt, hvor der er brug for det.
# 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()Hurtigt tjek
Test din forståelse af begreberne i Data Structures & Algorithms — Coding Interview Prep fra denne lektion.
Opsummering af lektionen
I denne lektion lærte du: En monoton stak opretholder stigende eller faldende rækkefølge ved at fjerne elementer, der bryder invarianten, før et nyt element lægges på stakken, en aftagende stak besvarer spørgsmål om næste eller forrige større element, mens en stigende stak besvarer spørgsmål om næste eller forrige mindre element, og hvert element lægges på og fjernes fra stakken højst én gang, hvilket giver O(n) samlet tid — ikke O(n²). Nu bruger vi den monotone stak til at finde det største rektangel i et histogram.
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Monoton stak: Stigende eller faldende” gratis?
Ja — hele teksten til “Monoton stak: Stigende eller faldende” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Monoton stak: Stigende eller faldende”?
Vedligehold en stigende eller faldende stak for effektivt at besvare forespørgsler om næste større element og forrige mindre element i O(n). Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “Monoton stak: Stigende eller faldende”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Monoton stak: Stigende eller faldende
- Største rektangel i et histogram
- Maksimum i skydevindue med en monoton deque
- Opsamling af regnvand: Stak og to pegere