𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟱: 𝗕𝗲𝘀𝘁 𝗧𝗶𝗺𝗲 𝘁𝗼 𝗕𝘂𝘆 𝗮𝗻𝗱 𝗦𝗲𝗹𝗹 𝗦𝘁𝗼𝗰𝗸
Leetcode 121 meminta Anda untuk menemukan waktu terbaik untuk membeli dan menjual saham. Anda mendapatkan sebuah array berisi harga. Setiap indeks mewakili satu hari. Nilainya adalah biaya pada hari tersebut.
Tujuannya sederhana. Beli pada satu hari dan jual pada hari di masa mendatang untuk mendapatkan keuntungan maksimal. Jika tidak ada keuntungan yang memungkinkan, kembalikan 0.
Batasan Masalah:
- Panjang array hingga 100.000.
- Harga hingga 10.000.
- Anda harus menjual setelah membeli.
Pendekatan 1: Metode Naif (Brute Force)
Cara brute force memeriksa setiap pasangan beli dan jual. Ini menggunakan dua loop.
- Kompleksitas Waktu: O(n²)
- Masalah: Terlalu lambat.
Jika Anda memiliki 1.000 hari, Anda melakukan 1.000.000 pemeriksaan. Jika Anda memiliki 100.000 hari, Anda melakukan 10.000.000.000 pemeriksaan. Hal ini menyebabkan timeout di Leetcode.
Pendekatan 2: Metode yang Dioptimalkan (One Pass)
Anda dapat menyelesaikannya dalam satu kali iterasi (one pass) menggunakan dua variabel: minPrice dan maxProfit.
- Kompleksitas Waktu: O(n)
- Kompleksitas Ruang: O(1)
Cara kerjanya:
- Atur minPrice ke Infinity.
- Atur maxProfit ke 0.
- Lakukan loop pada setiap harga.
- Jika harga saat ini lebih rendah dari minPrice, perbarui minPrice.
- Jika harga saat ini dikurangi minPrice lebih besar dari maxProfit, perbarui maxProfit.
Penelusuran contoh dengan harga [7, 1, 5, 3, 6, 4]:
- Hari 1: Harga 7. minPrice menjadi 7. maxProfit tetap 0.
- Hari 2: Harga 1. minPrice menjadi 1. maxProfit tetap 0.
- Hari 3: Harga 5. 5 - 1 = 4. maxProfit menjadi 4.
- Hari 4: Harga 3. 3 - 1 = 2. maxProfit tetap 4.
- Hari 5: Harga 6. 6 - 1 = 5. maxProfit menjadi 5.
- Hari 6: Harga 4. 4 - 1 = 3. maxProfit tetap 5.
Jawaban Akhir: 5.
Versi yang dioptimalkan lebih unggul karena hanya memeriksa setiap harga satu kali. Ini berskala dengan baik untuk dataset yang besar.
Sumber: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1