Stock Span Problem
Ottieni il prezzo di chiusura di un'azione per ogni giorno: prices[i] è il prezzo del giorno i. L'intervallo del giorno i è il numero di giorni consecutivi, fino al giorno i incluso, in cui il prezzo è stato minore o uguale a prices[i].
Restituisci l'intervallo di ogni giorno, nello stesso ordine di prices. Ogni intervallo è almeno 1, perché un giorno conta sempre sé stesso.
Funzione
- pricesinteger-array
- il prezzo di ogni giorno, in ordine
- Restituisceinteger-array
- nell'arco di ogni giornata, nello stesso ordine
Vincoli
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- Un giorno precedente con lo stesso prezzo viene conteggiato nell’intervallo; solo un prezzo strettamente più alto lo interrompe.
Esempi
- Input
- prices = [31, 27, 14, 21, 30, 18, 40]
- Output
- [1, 1, 1, 2, 4, 1, 7]
- Spiegazione
- Il giorno 3, a 21, torna indietro oltre 14 e si ferma a 27: ampiezza 2. Il giorno 4, a 30, si ferma a 31: ampiezza 4. Il giorno 6, a 40, supera tutti i prezzi precedenti e copre tutti e 7 i giorni.
- Input
- prices = [8, 8, 3, 8]
- Output
- [1, 2, 1, 4]
- Spiegazione
- I prezzi uguali contano, quindi il giorno 1 a 8 copre il giorno 0 e ottiene 2. Il giorno 3 a 8 copre il 3 e i due 8 precedenti, per un intervallo di 4.
- Input
- prices = [50, 40, 30, 20]
- Output
- [1, 1, 1, 1]
- Spiegazione
- Ogni giorno è più economico del giorno precedente, quindi nessun intervallo risale oltre il giorno stesso e ogni intervallo è 1.
Per approfondire
I prezzi ora arrivano uno alla volta e devi comunicare ogni intervallo man mano che arriva il relativo prezzo. Quale approccio continua a funzionare e cosa conserva tra una chiamata e l’altra?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Contare all’indietro partendo da ogni giorno ripete il lavoro: per 8000 giorni allo stesso prezzo, l’ultimo giorno da solo torna indietro di 8000 giorni. Quando torni indietro da oggi, quali giorni precedenti puoi saltare definitivamente?
Una volta che il prezzo di oggi è almeno pari a quello di un giorno precedente, quel giorno precedente non potrà mai essere quello che interrompe un intervallo successivo: oggi è più vicino e costa almeno altrettanto. Contano solo i giorni più costosi di tutti quelli che li seguono, e i loro prezzi diminuiscono dal più vecchio al più recente.
Percorri i giorni in ordine e mantieni su uno stack, come indici, i giorni precedenti che contano ancora. Prima di rispondere per oggi, estrai tutti i giorni il cui prezzo è minore o uguale a quello di oggi. Uno stack vuoto significa che l’intervallo risale fino al giorno 0; altrimenti si ferma un giorno dopo quello rimasto in cima. Poi inserisci oggi.
Soluzione
L’intervallo di un giorno termina nel giorno precedente più vicino con un prezzo strettamente più alto. Tornare indietro per trovarlo costa fino a n passi per giorno. Invece, mantieni solo i giorni che possono ancora fermare un intervallo futuro: una pila di indici con prezzi strettamente decrescenti trova ogni confine in un’unica passata.
Conta all’indietro da ogni giorno
Corretto, ma non termina sui test più grandi
Intuizione
Segui la definizione. Per il giorno i, torna indietro di un giorno alla volta finché il prezzo in quel giorno è al massimo prices[i], contando anche il giorno i. Il primo prezzo strettamente più alto, oppure l’inizio dell’array, termina la sequenza.
Nessuna scansione riutilizza quella precedente. Con prezzi costanti o in aumento, ogni scansione torna indietro fino al giorno 0: n = 10^4 giorni significa circa 5 × 10^7 passaggi.
Algoritmo
- Crea
span, un array lungo quantoprices. - Per ogni giorno
i, imposta un contatore a 0 e un puntatorejai. - Mentre
j ≥ 0eprices[j] ≤ prices[i], aggiungi 1 al contatore e spostajindietro di un giorno. - Memorizza il contatore in
span[i]. Dopo l'ultimo giorno, restituiscispan.
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return spanPila monotona di giorni con valori più alti
Intuizione
Chiama blocco il giorno precedente più vicino con un prezzo strettamente più alto. L’intervallo è today - blocker, oppure today + 1 se non ce n’è nessuno.
Nel primo esempio, il giorno 3 costa 21 e il giorno 4 costa 30. Ogni percorso successivo raggiunge prima il giorno 4 e qualsiasi prezzo che supera 30 supera anche 21, quindi il giorno 3 non potrà mai più bloccare. In generale, quando arriva il giorno di oggi, ogni candidato precedente con un prezzo minore o uguale a quello di oggi è terminato: rimuovilo. Il giorno rimasto in cima è il blocco di oggi. Poi inserisci oggi.
I prezzi nella pila diminuiscono strettamente dal basso verso l’alto, quindi il primo che rimane è il prezzo più alto più vicino. Nel primo esempio, il giorno 4 rimuove i giorni 3 e 1 e si ferma al giorno 0, per un intervallo di 4 - 0 = 4. Ogni giorno viene inserito una volta e rimosso al massimo una volta, quindi il passaggio richiede O(n).
Algoritmo
- Crea l’array
spane uno stack vuoto per gli indici dei giorni. - Per ogni giorno
today, estrai gli indici dallo stack finché il loro prezzo è minore o uguale aprices[today]. - Se lo stack è vuoto, lo span è
today + 1; altrimenti ètodaymeno l’indice in cima. - Inserisci
todaynello stack e passa al giorno successivo. Restituiscispan.
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
Trappole e casi limite
- Fare un pop su
<invece che su<=. In[8, 8, 3, 8]l’ultimo giorno ha uno span di 4; fermandosi all’8 precedente si ottiene 2. - Scrivere
todayinvece ditoday + 1quando lo stack è vuoto. Il giorno 0 deve ottenere 1, non 0. - Fare pop solo una volta al giorno. Nel primo esempio 40 deve eliminare i giorni 5, 4 e 0. Fermandosi dopo il giorno 5, il giorno 4 sembra il suo blocco, per uno span di 2 invece di 7.
- In Lua e R, gli array iniziano da 1. Con indici a base 1, lo span con lo stack vuoto è
today, nontoday + 1.
Domande frequenti4
Qual è la complessità temporale del problema dello stock span?
Tempo O(n) e spazio aggiuntivo O(n) con lo stack monotono, poiché ogni giorno lascia lo stack al massimo una volta. Scorrere all’indietro partendo da ogni giorno richiede O(n²) quando i prezzi continuano a salire o restano invariati.
Lo stack dovrebbe memorizzare i prezzi o gli indici dei giorni?
Indici dei giorni. L'intervallo è un conteggio di giorni, e solo l'indice del blocco te lo fornisce. prices[index] recupera il prezzo per il confronto.
È possibile risolvere il problema dello stock span senza uno stack separato?
Sì. Inizia da j = today - 1; mentre j ≥ 0 e prices[j] ≤ prices[today], salta a j - span[j], poiché ogni giorno all'interno di quell'intervallo ha un prezzo al massimo pari a prices[j]. L'intervallo è today - j. I salti terminano solo nei giorni che sarebbero mantenuti nello stack, quindi il passaggio rimane O(n).
Il problema dello stock span è un problema del precedente elemento maggiore?
Sì, misurata in giorni: per ogni giorno trovi il giorno precedente più vicino con un prezzo strettamente più alto e indichi quanto è distante. Invertendo la direzione della scansione o il confronto, la stessa pila restituisce il successivo maggiore, il successivo minore o il precedente minore.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def stockSpan(prices):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
prices = [31, 27, 14, 21, 30, 18, 40]
Output atteso
[1, 1, 1, 2, 4, 1, 7]