𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗚𝗶𝗼𝗿𝗻𝗼 𝟱: 𝗠𝗲𝗴𝗹𝗶𝗼𝗿 𝗺𝗼𝗺𝗲𝗻𝘁𝗼 𝗽𝗲𝗿 𝗮𝗰𝗾𝘂𝗶𝘀𝘁𝗮𝗿𝗲 𝗲 𝘃𝗲𝗻𝗱𝗲𝗿𝗲 𝗮𝗰𝗰𝗶𝗼𝗻𝗶
Leetcode 121 ti chiede di trovare il miglior momento per acquistare e vendere un'azione. Ricevi un array di prezzi. Ogni indice rappresenta un giorno. Il valore è il costo in quel giorno.
L'obiettivo è semplice. Comprare in un giorno e vendere in un giorno futuro per ottenere il massimo profitto. Se non è possibile ottenere alcun profitto, restituisci 0.
Vincoli del problema:
- Lunghezza dell'array fino a 100.000.
- Prezzi fino a 10.000.
- Devi vendere dopo aver acquistato.
Approccio 1: Il metodo ingenuo (Brute Force)
Il metodo brute force controlla ogni singola coppia di acquisto e vendita. Questo utilizza due cicli.
- Complessità temporale: O(n²)
- Problema: È troppo lento.
Se hai 1.000 giorni, esegui 1.000.000 di controlli. Se hai 100.000 giorni, esegui 10.000.000.000 di controlli. Questo causa un timeout su Leetcode.
Approccio 2: Il metodo ottimizzato (One Pass)
Puoi risolvere questo problema in un unico passaggio utilizzando due variabili: minPrice e maxProfit.
- Complessità temporale: O(n)
- Complessità spaziale: O(1)
Come funziona:
- Imposta minPrice a infinito.
- Imposta maxProfit a 0.
- Cicla attraverso ogni prezzo.
- Se il prezzo corrente è inferiore a minPrice, aggiorna minPrice.
- Se il prezzo corrente meno minPrice è maggiore di maxProfit, aggiorna maxProfit.
Esempio di esecuzione con i prezzi [7, 1, 5, 3, 6, 4]:
- Giorno 1: Prezzo 7. minPrice diventa 7. maxProfit rimane 0.
- Giorno 2: Prezzo 1. minPrice diventa 1. maxProfit rimane 0.
- Giorno 3: Prezzo 5. 5 - 1 = 4. maxProfit diventa 4.
- Giorno 4: Prezzo 3. 3 - 1 = 2. maxProfit rimane 4.
- Giorno 5: Prezzo 6. 6 - 1 = 5. maxProfit diventa 5.
- Giorno 6: Prezzo 4. 4 - 1 = 3. maxProfit rimane 5.
Risposta finale: 5.
La versione ottimizzata vince perché analizza ogni prezzo una sola volta. Si scala bene con dataset di grandi dimensioni.
Fonte: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1