Stack monotono: crescente e decrescente
Mantenga uno stack crescente o decrescente per rispondere in modo efficiente alle query next-greater-element e previous-smaller-element in O(n).
Stack monotono: crescente e decrescente è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos'è uno stack monotono
Uno stack monotono è uno stack che mantiene i propri elementi in ordine crescente o decrescente, dal fondo alla cima. Prima di inserire un nuovo elemento, rimuoviamo tutti gli elementi che violano l'invariante di monotonia. Questa struttura vincolata permette di risolvere in O(n) problemi che altrimenti richiederebbero cicli annidati con complessità O(n²).
L'intuizione chiave è che ogni elemento viene inserito e rimosso al massimo una volta, quindi il numero totale di operazioni durante l'attraversamento dell'intero array è O(n), non O(n²). Nel momento in cui rimuoviamo un elemento, troviamo la risposta che stava aspettando.
# 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
Il problema Next Greater Element richiede, per ogni elemento, di trovare il primo elemento maggiore alla sua destra. Un doppio ciclo a forza bruta O(n²) è troppo lento. Con uno stack monotono decrescente, il problema si risolve in O(n).
Si elaborano gli elementi da sinistra a destra. Prima di inserire l'elemento i, si rimuovono dallo stack tutti gli elementi minori di nums[i]: nums[i] è il next greater element per ciascuno di essi. Dopo aver elaborato tutti gli elementi, quelli rimasti nello stack non hanno alcun elemento maggiore alla loro destra (risposta = -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]Elemento maggiore successivo: tracciare l'algoritmo
Tracciamo [2, 1, 2, 4, 3] passo dopo passo. Manteniamo uno stack decrescente di indici per i quali non è ancora stato trovato l'elemento maggiore successivo.
- i=0, val=2: stack vuoto, inseriamo 0. Stack: [0]
- i=1, val=1: 1 < nums[0]=2, inseriamo 1. Stack: [0,1]
- i=2, val=2: rimuoviamo 1 (nums[1]=1 < 2), result[1]=2; ora nums[0]=2 non è < 2, inseriamo 2. Stack: [0,2]
- i=3, val=4: rimuoviamo 2 (result[2]=4), rimuoviamo 0 (result[0]=4), inseriamo 3. Stack: [3]
- i=4, val=3: 3 < nums[3]=4, inseriamo 4. Stack: [3,4]
- Fine: gli elementi nello stack [3,4] hanno 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])Elemento minore precedente
Gli stack monotoni consentono anche di rispondere alle query sull'elemento minore precedente (PSE): per ogni elemento, l'elemento più vicino alla sua sinistra che sia minore. Anziché rimuovere gli elementi quando se ne incontra uno maggiore, rimuoviamo gli elementi quando se ne incontra uno maggiore o uguale e registriamo la cima dello stack come PSE prima di inserire il nuovo elemento.
Cambia la direzione dell'elaborazione: procediamo comunque da sinistra a destra, ma invece di rispondere alle domande mentre rimuoviamo gli elementi, rispondiamo subito prima di inserirli. La cima dello stack in quel momento è l'elemento minore più vicino alla sinistra. Se lo stack è vuoto, non esiste alcun elemento minore alla sinistra (risposta = -1 o una sentinella).
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]Temperature giornaliere: attendere i giorni più caldi
Il problema Daily Temperatures (LeetCode 739): date le temperature giornaliere, restituisca un array in cui ogni elemento indica il numero di giorni che mancano a una temperatura più alta. È esattamente lo schema dell'elemento maggiore successivo, ma invece del valore maggiore vogliamo il numero di giorni (la differenza tra gli indici).
Utilizzi uno stack monotono decrescente di indici. Quando troviamo una temperatura più alta all'indice i, rimuoviamo tutti gli indici j dallo stack per i quali temps[j] < temps[i] e impostiamo result[j] = i - j. Gli indici rimanenti non hanno alcun giorno futuro più caldo (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]Stack crescente o decrescente: quando usare ciascuno
Scegliere la direzione corretta dello stack è fondamentale:
- Stack monotono decrescente (rimuovere quando current > top): risponde alle query sull'elemento maggiore successivo e sull'elemento maggiore precedente. Viene utilizzato in daily-temperatures, largest-rectangle e trap-rain-water.
- Stack monotono crescente (rimuovere quando current < top): risponde alle query sull'elemento minore successivo e sull'elemento minore precedente. Viene utilizzato per trovare lo span dei prezzi azionari e il numero di persone visibili in una coda.
Ricordi: l'elemento che causa una rimozione è la risposta alla query dell'elemento rimosso: è l'elemento maggiore successivo oppure quello minore successivo, a seconda dell'invariante mantenuto.
# 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)Elemento maggiore successivo in un array circolare
Next Greater Element II (LeetCode 503): dato un array circolare (con ritorno all'inizio), troviamo l'elemento maggiore successivo. Il trucco consiste nell'elaborare l'array due volte raddoppiando gli indici: iteriamo da 0 a 2n-1 e utilizziamo index % n per tornare all'inizio. Inseriamo nello stack solo gli indici da 0 a n-1 (prima passata), così non li contiamo due volte.
In alternativa, nella seconda passata elaboriamo l'array senza inserire nuovi indici, ma eseguendo solo rimozioni. In questo modo gestiamo correttamente la ricerca circolare senza duplicare realmente l'array e manteniamo lo spazio a 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]Problema dello span dei prezzi azionari
Il problema dello Stock Span: dati i prezzi azionari giornalieri, calcoli lo span di ogni giorno, cioè il numero di giorni consecutivi precedenti con un prezzo minore o uguale a quello di oggi. È il problema dell'elemento maggiore precedente presentato in forma diversa: lo span è la distanza tra oggi e il giorno più vicino con un prezzo strettamente maggiore.
Utilizzi uno stack monotono decrescente. Durante l'elaborazione del giorno i, rimuova tutti i giorni con un prezzo ≤ current. Lo span è i - stack[-1] se lo stack non è vuoto, oppure i + 1 se è vuoto (il prezzo è il massimo raggiunto finora). Poi inserisca 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 = 6Stack monotono per le persone visibili in una coda
Il problema Number of Visible People in a Queue: le persone stanno in una coda e ciascuna ha una determinata altezza. La persona i può vedere la persona j (j > i) se tutte le persone tra loro sono più basse di entrambe. Per risolvere questo problema si utilizza uno stack monotono decrescente.
Si procede da destra a sinistra. Si mantiene uno stack decrescente di altezze. Per ogni persona, si conta quante persone può vedere: si rimuovono tutte le persone più basse (visibili, ma che in seguito vengono coperte), più 1 se dopo le rimozioni lo stack non è vuoto (anche la prima persona più alta è visibile). Il costo complessivo è O(n), perché ogni persona viene inserita e rimossa al massimo una volta.
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]Garanzia O(n): perché ogni elemento viene inserito e rimosso al massimo una volta
La garanzia di tempo O(n) degli algoritmi con stack monotoni deriva da un semplice argomento di ammortamento: ogni elemento viene inserito nello stack esattamente una volta e rimosso al massimo una volta. Nessun elemento può essere inserito o rimosso più di una volta. Pertanto, il numero totale di operazioni di inserimento e rimozione nell'intero ciclo è al massimo 2n, con un lavoro complessivo O(n), nonostante il ciclo while annidato sembri suggerire O(n²).
È importante saper esporre questa analisi ammortizzata durante i colloqui. Il ciclo while non viene eseguito n volte a ogni iterazione: viene eseguito solo il numero di volte necessario per rimuovere gli elementi che erano in attesa, e tali elementi scompaiono definitivamente dopo essere stati rimossi.
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 <= 2nRiconoscere i problemi con stack monotoni
Un problema probabilmente richiede uno stack monotono se chiede l'elemento maggiore o minore più vicino, lo span dei prezzi, gli elementi visibili in una fila oppure aree basate su un istogramma. Cerchi queste parole chiave e questi schemi: per ogni elemento serve la risposta fornita dall'elemento rilevante più vicino in una direzione (a sinistra o a destra).
Se una soluzione a forza bruta esegue una scansione verso sinistra o verso destra per ogni elemento (O(n²)), sostituisca quella scansione con uno stack monotono. Lo stack “memorizza” le risposte candidate, scarta quelle irrilevanti ed esegue il pop della risposta corretta esattamente nel momento in cui serve.
# 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()Verifica rapida
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: uno stack monotono mantiene un ordine crescente o decrescente rimuovendo gli elementi che violano l'invariante prima di inserirli, uno stack decrescente risponde alle query sull'elemento maggiore successivo o precedente, mentre uno stack crescente risponde alle query sull'elemento minore successivo o precedente e ogni elemento viene inserito e rimosso al massimo una volta, garantendo un tempo totale O(n), non O(n²). Ora applichiamo lo stack monotono per trovare il rettangolo più grande in un istogramma.
Domande Frequenti
La lezione «Stack monotono: crescente e decrescente» è gratuita?
Sì — il testo completo di «Stack monotono: crescente e decrescente» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Stack monotono: crescente e decrescente»?
Mantenga uno stack crescente o decrescente per rispondere in modo efficiente alle query next-greater-element e previous-smaller-element in O(n). Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Stack monotono: crescente e decrescente»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Stack monotono: crescente e decrescente
- Rettangolo più grande nell'istogramma
- Massimo in una finestra scorrevole con deque monotona
- Trapping Rain Water: stack e due puntatori