Best Time to Buy and Sell Stock
Ti viene fornita una lista prices, dove prices[i] è il prezzo di un’azione nel giorno i. Puoi acquistare un’azione in un giorno e venderla in un giorno successivo. Restituisci il profitto massimo che puoi ottenere, oppure 0 se ogni possibile operazione comporta una perdita.
Funzione
- pricesinteger-array
- il prezzo del titolo per ogni giorno, in ordine
- Restituisceinteger
- il profitto massimo ottenuto da un acquisto e da una vendita successiva, oppure 0
Vincoli
1 ≤ prices.length ≤ 1050 ≤ prices[i] ≤ 104- Effettui al massimo una transazione e vendi in un giorno successivo a quello in cui acquisti.
Esempi
- Input
- prices = [7, 2, 5, 9, 1, 4]
- Output
- 7
- Spiegazione
- Acquista il giorno 1 a 2 e vendi il giorno 3 a 9 per un profitto di 7. Il prezzo più basso, 1 il giorno 4, viene dopo il 9, quindi la vendita migliore successiva frutta solo 3.
- Input
- prices = [9, 7, 4, 3, 1]
- Output
- 0
- Spiegazione
- Il prezzo scende ogni giorno, quindi ogni vendita sarebbe inferiore al prezzo di acquisto. Non fai trading e il profitto è 0.
Per approfondire
Che cosa succederebbe se potessi fare tutti gli scambi che vuoi, detenendo al massimo un’azione alla volta?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
La vendita viene sempre dopo l'acquisto. Scegli un giorno per vendere: quale giorno per comprare dà il profitto maggiore?
Per un determinato giorno di vendita, il giorno migliore per acquistare è il giorno più economico che lo precede. Non devi cercare di nuovo quel giorno ogni volta se te lo ricordi mentre procedi.
Esamina i giorni in ordine e tieni traccia di due numeri: il prezzo più basso finora e il profitto migliore finora. Ogni giorno, confronta il prezzo di oggi meno il prezzo più basso con il profitto migliore, quindi aggiorna il prezzo più basso.
Soluzione
Devi comprare prima di vendere, quindi la risposta non è il prezzo più alto meno quello più basso. Per ogni giorno in cui potresti vendere, l’acquisto migliore è nel giorno più economico precedente. Tenendo traccia del prezzo più basso mentre procedi, il problema si riduce a un’unica passata.
Prova ogni coppia di acquisto e vendita
Corretto, ma non termina sui test più grandi
Intuizione
Ogni operazione prevede un giorno in cui comprare e un giorno successivo in cui vendere, quindi prova ogni coppia e conserva la differenza maggiore. Iniziare il profitto migliore da 0 tiene conto della possibilità di non effettuare operazioni. Vengono controllate tutte le operazioni consentite, quindi la risposta è corretta.
Una lista di n prezzi ha circa n²/2 coppie: 100,000 giorni significano circa 5 miliardi di sottrazioni.
Algoritmo
- Imposta
besta 0. - Scorri ogni giorno di acquisto
buy. - Per ciascuno, scorri ogni giorno di vendita
sellsuccessivo. - Calcola
prices[sell]menoprices[buy]e memorizzalo inbestse è maggiore. - Restituisci
best.
def maxProfit(prices):
best = 0
n = len(prices)
for buy in range(n):
for sell in range(buy + 1, n):
best = max(best, prices[sell] - prices[buy])
return best
Un passaggio con il prezzo più basso finora
Intuizione
Fissa il giorno di vendita i. Il giorno migliore in cui aver comprato è il giorno più economico fino a i, quindi la migliore operazione che termina il giorno i frutta prices[i] meno il prezzo più basso incontrato finora. A ogni giorno di vendita corrisponde il suo giorno migliore per comprare, quindi il profitto più alto tra questi è la risposta. In un giorno in cui si registra un nuovo minimo, il profitto è 0, come se non si facesse alcuna operazione.
La scansione legge ogni prezzo una sola volta e mantiene due numeri, lowest e best: tempo O(n) e spazio O(1).
Algoritmo
- Imposta
lowestal primo prezzo ebesta 0. - Esamina i prezzi in ordine.
- Se il prezzo corrente è inferiore a
lowest, impostalo come nuovolowest. - Calcola il prezzo corrente meno
loweste memorizzalo inbestse è maggiore. - Restituisci
best.
def maxProfit(prices):
lowest = prices[0]
best = 0
for price in prices:
if price < lowest:
lowest = price
elif price - lowest > best:
best = price - lowest
return best
Trappole e casi limite
- Restituire il prezzo più alto meno quello più basso. In
[7, 2, 5, 9, 1, 4]il risultato è 8, ma l'1 viene dopo il 9. La risposta è 7. - Lasciare che la risposta diventi negativa. In
[9, 7, 4, 3, 1]la differenza migliore è -1; inizializzabesta 0, non alla prima differenza. - Inizializzare
lowesta 0. Ogni profitto sarà quindi uguale al prezzo stesso, perciò[9, 7, 4, 3, 1]restituisce 9. Inizializzalo al primo prezzo.
Domande frequenti3
Qual è la complessità temporale di Best Time to Buy and Sell Stock?
La soluzione in un solo passaggio richiede un tempo O(n) per n giorni, perché legge ogni prezzo una volta, e uno spazio aggiuntivo O(1): il prezzo più basso finora e il profitto migliore. Provare ogni coppia di giorni richiede un tempo O(n²).
Perché non sottrarre il prezzo più basso da quello più alto?
Il prezzo più basso può arrivare dopo quello più alto e devi comprare prima di vendere. In [7, 2, 5, 9, 1, 4] l'1 viene dopo il 9, quindi la migliore operazione consentita consiste nel comprare a 2 e vendere a 9, ottenendo 7.
Il problema “Best Time to Buy and Sell Stock” è un problema di programmazione dinamica?
Puoi leggerlo in entrambi i modi. Il prezzo più basso finora è un piccolo dato di stato che aggiorni ogni giorno: questa è la prospettiva della programmazione dinamica. Abbinare ogni vendita al giorno precedente più conveniente è la prospettiva greedy. Entrambi portano allo stesso codice in un solo passaggio.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def maxProfit(prices):
# Scrivi il codice quiTest #1
Test #2
Argomento
prices = [7, 2, 5, 9, 1, 4]
Output atteso
7