Schema dello stack monotono

Una pila monotona è una pila che mantiene un invariante di ordinamento tra i propri elementi. Una pila monotona crescente contiene elementi crescenti dal fondo verso la cima; una pila monotona decrescente contiene elementi decrescenti dal fondo verso la cima. Quando un nuovo elemento viola l'invariante, gli elementi vengono estratti finché l'invariante non è ripristinato, quindi il nuovo elemento viene inserito.

Questo semplice meccanismo consente di rispondere in O(n) alle query sull'elemento maggiore più vicino e sull'elemento minore più vicino, che con un approccio ingenuo richiederebbero cicli annidati in O(n²).

Per ogni elemento, trovi il primo elemento strettamente maggiore alla sua destra. Un approccio brute force in O(n²) esegue una scansione verso destra a partire da ogni posizione. L'approccio con pila monotona mantiene una pila decrescente di indici. Quando viene incontrato un elemento maggiore, rimuove tutti gli indici degli elementi più piccoli: l'elemento maggiore successivo per ciascuno di essi è l'elemento corrente. Gli indici rimanenti non hanno alcun elemento maggiore successivo (la risposta è -1).

LeetCode 503 «Next Greater Element II»: lo stesso problema, ma l'array viene considerato circolare. Dopo aver raggiunto la fine, si torna all'inizio e si continua la ricerca. Il trucco consiste nell'iterare due volte sull'array (dagli indici 0 a 2n-1) e usare i % n per accedere all'array originale. Inserisca nella pila solo gli indici nell'intervallo [0, n-1] per evitare di elaborare duplicati.

Riprendiamo LeetCode 739: per ogni giorno, quanti giorni devono trascorrere prima di trovare una temperatura più alta? La pila monotona contiene gli indici dei giorni con temperature in ordine decrescente. Quando viene trovato un giorno più caldo i, rimuova dalla pila tutti gli indici j dei giorni più freddi e registri result[j] = i - j. I giorni rimasti nella pila non hanno mai trovato un giorno più caldo, quindi il loro risultato resta 0.

La query sull'elemento minore precedente chiede: per ogni elemento, qual è il valore minore più vicino alla sua sinistra? Utilizzi una pila monotona crescente, elaborando gli elementi da sinistra a destra. Prima di inserire l'indice i, la cima della pila contiene l'elemento minore precedente, perché tutti gli elementi maggiori di nums[i] erano già stati rimossi durante gli inserimenti precedenti, quando elementi maggiori li avevano fatti rimuovere.

LeetCode 84 «Largest Rectangle in Histogram»: una pila monotona crescente di indici. Per ogni barra, rimuova tutte le barre più alte di quella corrente. Per ogni barra estratta h, il suo limite destro è l'indice corrente i e il suo limite sinistro è la nuova cima della pila + 1 (oppure 0 se la pila è vuota). Area = h × (right - left). Aggiunga una sentinella di altezza 0 per forzare l'estrazione di tutte le barre rimanenti alla fine.

LeetCode 85 «Maximal Rectangle» estende il problema dell'istogramma a una matrice binaria 2D. Per ogni riga, calcoli le altezze accumulate delle barre: se matrix[row][col] == '1', l'altezza è il numero di 1 consecutivi sopra questa cella e includendo questa cella. Applichi quindi l'algoritmo del «rettangolo più grande nell'istogramma» all'array delle altezze di ogni riga. Complessità temporale: O(m × n) per una matrice m×n.

LeetCode 42 «Trapping Rain Water» con una pila: mantenga una pila decrescente di indici. Quando viene incontrata una barra più alta, si forma una conca. Rimuova il fondo della conca; calcoli la larghezza dell'acqua come (current_index - stack_top - 1) e l'altezza come (min(current_bar, new_stack_top_bar) - valley_height). Sommi tutti i contributi. Complessità temporale: O(n), spazio: O(n).

Segnali che indicano che una pila monotona è lo strumento giusto: il problema chiede l'elemento maggiore o minore successivo o precedente, la risposta per ogni elemento dipende dagli elementi in una direzione specifica oppure una soluzione ingenua in O(n²) richiede una scansione a sinistra o a destra per ogni elemento. La pila conserva i candidati che potrebbero essere le risposte per gli elementi futuri e li scarta non appena arriva un candidato migliore.

Decida sempre in anticipo: crescente (per l'elemento minore successivo o precedente) oppure decrescente (per l'elemento maggiore successivo o precedente), oltre alla direzione di elaborazione.

Gli algoritmi con pila monotona possono sembrare inizialmente O(n log n) o O(n²) a causa del ciclo while annidato nel ciclo for. Tuttavia, ogni elemento viene inserito al massimo una volta ed estratto al massimo una volta. Il numero totale di operazioni di inserimento è n e anche il numero totale di operazioni di estrazione è al massimo n. Pertanto, considerando tutte le iterazioni, il lavoro totale è di 2n operazioni: O(n) ammortizzato, non O(n²).

Scelga la direzione della pila in base alla query. Per l'elemento maggiore successivo, utilizzi una pila decrescente: estragga gli elementi quando quello corrente è maggiore. Per l'elemento minore successivo, utilizzi una pila crescente: estragga gli elementi quando quello corrente è minore. Per il rettangolo più grande, utilizzi una pila crescente ed estragga gli elementi quando compare una barra più bassa. Per il massimo in una finestra scorrevole, utilizzi una deque decrescente e rimuova gli elementi da entrambe le estremità.

Scrivere l'invariante in un commento prima di iniziare a programmare chiarisce la logica e velocizza il debug.

Verifichi la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha appreso che: una pila monotona mantiene un invariante ordinato rimuovendo gli elementi che lo violano prima di inserire il nuovo elemento, le pile decrescenti rispondono alle query sull'elemento maggiore successivo, mentre le pile crescenti rispondono alle query sull'elemento minore successivo e il tempo totale è O(n) ammortizzato perché ogni elemento viene inserito ed estratto al massimo una volta. Nella prossima lezione implementeremo code usando pile e pile usando code.