Stack monotono: elemento successivo maggiore
Rispondere alle query sugli intervalli in un’unica passata
Stack monotono: elemento successivo maggiore è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 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.
Il problema del prossimo maggiore
Per ogni numero, vuole trovare il primo valore maggiore alla sua destra. La brute force richiede O(n al quadrato), ma uno stack monotono risolve il problema in un'unica scansione.
Che cosa significa monotono
Uno stack monotono mantiene i propri valori ordinati, in questo caso in ordine decrescente, così appena quell'ordine verrebbe violato sappiamo di aver trovato una risposta.
Memorizzare gli indici, non i valori
Inserisca nello stack gli indici invece dei numeri originali. In questo modo saprà esattamente quale posizione riempire quando compare un elemento maggiore.
stack = []
ans = [-1] * len(nums)Scorrere da sinistra a destra
Scorra l'array una sola volta. A ogni indice, estrarrà gli elementi per cui è stata trovata una risposta oppure inserirà l'indice corrente per elaborarlo in seguito.
for i in range(len(nums)):Estrarre gli elementi più piccoli
Finché il valore corrente supera il valore all'indice in cima, quell'indice ha finalmente trovato il proprio elemento successivo maggiore.
while stack and nums[i] > nums[stack[-1]]:Registrare la risposta
Estragga l'indice in cima e imposti la sua risposta sul valore corrente. Ogni indice viene risolto esattamente una volta, mantenendo il lavoro lineare.
j = stack.pop()
ans[j] = nums[i]Inserire e continuare
Dopo aver risolto tutti gli elementi più piccoli, inserisca l'indice corrente, che resterà in attesa del proprio elemento maggiore futuro.
stack.append(i)Gli elementi rimasti non hanno risposta
Gli indici ancora nello stack alla fine non hanno mai incontrato un valore maggiore. Mantengono il valore predefinito -1, che significa che non ne esiste alcuno.
Perché è O(n)
Ogni indice viene inserito una volta ed estratto una volta. Anche con il ciclo while interno, il lavoro totale resta lineare nell'intera scansione.
Invertire per trovare il successivo minore
Le serve invece l'elemento successivo minore? Mantenga lo stack in ordine crescente, invertendo il confronto da maggiore di a minore di.
while stack and nums[i] < nums[stack[-1]]:Un modello, non un trucco
Intervalli, prezzi azionari e aree degli istogrammi riutilizzano tutti questa idea. Lo stack monotono è un modello fondamentale delle gare di programmazione che vale la pena memorizzare.
Verifica rapida
Sta risolvendo il problema del next-greater-element con uno stack monotono. Perché il tempo totale è lineare?
Riepilogo: una scansione, molte risposte
Ha usato uno stack monotono decrescente di indici per trovare gli elementi successivi maggiori in O(n). Questo modello è utile per molti problemi sugli intervalli. 🚀
Domande Frequenti
La lezione «Stack monotono: elemento successivo maggiore» è gratuita?
Sì — il testo completo di «Stack monotono: elemento successivo maggiore» è 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: elemento successivo maggiore»?
Rispondere alle query sugli intervalli in un’unica passata 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 2 di 4.
Quanto tempo richiede la lezione «Stack monotono: elemento successivo maggiore»?
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 per le parentesi corrispondenti
- Stack monotono: elemento successivo maggiore
- Code e collections.deque
- Massimo di una finestra scorrevole con Deque