Forberedelse til kodeintervjuer · leksjon

Monoton stakk: økende eller avtakende

Vedlikehold en økende eller avtakende stakk for effektivt å svare på spørsmål om neste større element og forrige mindre element i O(n).

Leksjon 1 av 413 trinn

Monoton stakk: økende eller avtakende er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hva er en monoton stakk

En monoton stakk er en stakk som opprettholder en sortert rekkefølge for elementene sine, enten alltid økende fra bunn til topp eller alltid avtakende. Før et nytt element legges på, fjernes alle elementer som bryter den monotone invarianten. Denne begrensede datastrukturen muliggjør O(n)-løsninger på problemer som ellers ville krevd nestede løkker med O(n²).

Den viktige innsikten er at hvert element legges på og tas av stakken høyst én gang. Derfor er det totale antallet operasjoner gjennom hele gjennomgangen av arrayet O(n), ikke O(n²). I det øyeblikket et element tas av stakken, har vi funnet svaret det ventet 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]

Neste større element I

Problemet med neste større element går ut på å finne det første elementet til høyre som er større, for hvert element. En naiv dobbeltløkke med O(n²) er for langsom. Med en monoton avtakende stakk løses dette på O(n).

Behandle elementene fra venstre mot høyre. Før element i legges på, fjernes alle elementene fra stakken som er mindre enn nums[i] — nums[i] er det neste større elementet for alle disse. Etter at alle elementene er behandlet, har de gjenværende elementene på stakken ikke noe større element til høyre (svaret = -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]

Neste større element: gjennomgang av algoritmen

La oss gå gjennom [2, 1, 2, 4, 3] trinn for trinn. Vi vedlikeholder en avtakende stakk med indekser der det neste større elementet ennå ikke er funnet.

i=0, val=2: stakken er tom, legg 0 på stakken. Stakk: [0]
i=1, val=1: 1 < nums[0]=2, legg 1 på stakken. Stakk: [0,1]
i=2, val=2: ta 1 av stakken (nums[1]=1 < 2), result[1]=2; nå er nums[0]=2 ikke < 2, legg 2 på stakken. Stakk: [0,2]
i=3, val=4: ta 2 av stakken (result[2]=4), ta 0 av stakken (result[0]=4), legg 3 på stakken. Stakk: [3]
i=4, val=3: 3 < nums[3]=4, legg 4 på stakken. Stakk: [3,4]
Slutt: elementene i stakken [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 stabler kan også besvare forespørsler om forrige mindre element (PSE): for hvert element finner vi det nærmeste elementet til venstre som er mindre. I stedet for å ta elementer av stakken når vi møter et større element, tar vi dem av når vi møter et større eller likt element, og registrerer toppen av stakken som PSE før vi legger det nye elementet på stakken.

Retningen på når vi besvarer spørsmålene, endres: Vi behandler fortsatt elementene fra venstre mot høyre, men i stedet for å besvare spørsmål når vi tar elementer av stakken, gjør vi det rett før vi legger et element på stakken. Toppen av stakken på dette tidspunktet er det nærmeste mindre elementet til venstre. Hvis stakken er tom, finnes det ikke noe mindre element til venstre (svaret er -1 eller en vaktverdi).

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: venting på varmere dager

Problemet Daily Temperatures (LeetCode 739): Gitt daglige temperaturer skal De returnere en array der hvert element angir hvor mange dager det er til temperaturen blir høyere. Dette er nøyaktig samme mønster som for neste større element, men i stedet for den større verdien ønsker vi antall dager (indeksforskjellen).

Bruk en monoton avtakende stakk med indekser. Når vi finner en varmere temperatur ved indeks i, tar vi alle indekser j av stakken der temps[j] < temps[i], og setter result[j] = i - j. Indeksene som blir igjen, har ingen varmere dag i fremtiden (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]

Økende og avtakende stakk: når hver av dem brukes

Det er avgjørende å velge riktig retning på stakken:

Monoton avtakende stakk (ta av når current > top): besvarer forespørsler om neste større element og forrige større element. Brukes i daily-temperatures, largest-rectangle og trap-rain-water.
Monoton økende stakk (ta av når current < top): besvarer forespørsler om neste mindre element og forrige mindre element. Brukes til å finne spennet for aksjekurser og antallet synlige personer i en kø.

Husk: Elementet som fører til at et annet element tas av stakken, er svaret på forespørselen til elementet som tas av — enten det neste større eller det neste mindre elementet, avhengig av hvilken invariant De opprettholder.

# 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)

Sirkulært neste større element

Next Greater Element II (LeetCode 503): Gitt en sirkulær array, der slutten følges av begynnelsen, skal De finne det neste større elementet. Trikset er å behandle arrayen to ganger ved å doble indeksene: iterer fra 0 til 2n-1 og bruk index % n for å gå rundt. Vi legger bare indekser fra 0 til n-1 på stakken (i første gjennomgang), slik at vi ikke teller elementene dobbelt.

Alternativt kan De behandle den andre gjennomgangen uten å legge nye indekser på stakken — da tar De bare elementer av stakken. Dette håndterer oppslaget rundt slutten korrekt uten faktisk å duplisere arrayen, og beholder plasskompleksiteten 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 med aksjespenn

Stock Span-problemet: Gitt daglige aksjekurser skal De beregne spennet for hver dag — antallet sammenhengende foregående dager med en kurs som er mindre enn eller lik dagens kurs. Dette er egentlig problemet med forrige større element: Spennet er avstanden fra dagens dag tilbake til den nærmeste dagen med en strengt høyere kurs.

Bruk en monoton avtakende stakk. Når dag i behandles, tar De alle dager med kurs ≤ dagens kurs av stakken. Spennet er i - stack[-1] hvis stakken ikke er tom, eller i + 1 hvis den er tom (kursen er den høyeste så langt). Legg deretter 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 = 6

Monoton stakk for synlige personer i en kø

Problemet Number of Visible People in a Queue: Personer står i en kø, og hver person har en høyde. Person i kan se person j (j > i) hvis alle personene mellom dem er lavere enn begge. Dette løses med en monoton avtakende stakk.

Behandle personene fra høyre mot venstre. Vedlikehold en avtakende stakk med høyder. For hver person teller De hvor mange personer vedkommende kan se: Ta alle lavere personer av stakken (de er synlige, men blokkeres for videre personer), og legg til 1 hvis stakken ikke er tom etterpå (den første høyere personen er også synlig). Dette gir totalt O(n), fordi hver person legges på og tas av stakken maksimalt é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 legges på og tas av maksimalt én gang

O(n)-garantien for algoritmer med monoton stakk bygger på et enkelt amortisert argument: Hvert element legges på stakken nøyaktig én gang og tas av maksimalt én gang. Ingen elementer kan legges på eller tas av mer enn én gang. Derfor er det totale antallet operasjoner for å legge på og ta av elementer gjennom hele løkken høyst 2n, noe som gir O(n) arbeid totalt, selv om den nestede while-løkken kan se ut til å antyde O(n²).

Denne amortiserte analysen er viktig å kunne forklare i intervjuer. While-løkken kjører ikke n ganger per iterasjon — den kjører bare lenge nok til å ta elementene som har ventet, og disse elementene er borte for godt etter at de er tatt av.

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 <= 2n

Gjenkjenne problemer som kan løses med monoton stakk

Et problem trenger sannsynligvis en monoton stakk hvis det spør etter nærmeste større eller mindre element, spennet for kurser, synlige elementer på rekke eller arealer basert på histogrammer. Se etter disse nøkkelordene og mønstrene: Hvert element trenger svaret fra det nærmeste relevante elementet i én retning (mot venstre eller høyre).

Hvis en brute-force-løsning skanner mot venstre eller høyre fra hvert element (O(n²)), kan De erstatte denne skanningen med en monoton stakk. Stakken «husker» kandidatene, forkaster de irrelevante og tar ut det riktige svaret akkurat når det trengs.

# 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()

Hurtigsjekk

Test forståelsen Deres av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen har De lært at en monoton stakk opprettholder en økende eller avtakende rekkefølge ved å ta av elementer som bryter invarianten, før det nye elementet legges på, at en avtakende stakk besvarer spørsmål om neste eller forrige større element, mens en økende stakk besvarer spørsmål om neste eller forrige mindre element, og at hvert element legges på og tas av maksimalt én gang, noe som gir total kjøretid O(n) — ikke O(n²). Neste steg er å bruke den monotone stakken til å finne det største rektangelet i et histogram.

Gratis å komme i gang

Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 90
Leksjoner: 360

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Monoton stakk: økende eller avtakende» gratis?

Ja – hele teksten i «Monoton stakk: økende eller avtakende» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hva lærer jeg i «Monoton stakk: økende eller avtakende»?

Vedlikehold en økende eller avtakende stakk for effektivt å svare på spørsmål om neste større element og forrige mindre element i O(n). Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?

Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.

Hvor lang tid tar leksjonen «Monoton stakk: økende eller avtakende»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?

Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til Forberedelse til kodeintervjuer