𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟱: 𝗕𝗲𝘀𝘁 𝗧𝗶𝗺𝗲 𝘁𝗼 𝗕𝘂𝘆 𝗮𝗻𝗱 𝗦𝗲𝗹𝗹 𝗦𝘁𝗼𝗰𝗸
Leetcode 121 meminta anda mencari masa terbaik untuk membeli dan menjual saham. Anda diberikan satu tatasusunan harga. Setiap indeks mewakili satu hari. Nilainya adalah kos pada hari tersebut.
Matlamatnya mudah. Beli pada satu hari dan jual pada hari masa hadapan untuk mendapatkan keuntungan maksimum. Jika tiada keuntungan yang boleh diperoleh, pulangkan 0.
Kekangan Masalah:
- Panjang tatasusunan sehingga 100,000.
- Harga sehingga 10,000.
- Anda mesti menjual selepas membeli.
Pendekatan 1: Kaedah Naif (Brute Force)
Cara brute force menyemak setiap pasangan beli dan jual. Ini menggunakan dua gelung.
- Kompleksiti Masa: O(n²)
- Masalah: Ia terlalu lambat.
Jika anda mempunyai 1,000 hari, anda melakukan 1,000,000 semakan. Jika anda mempunyai 100,000 hari, anda melakukan 10,000,000,000 semakan. Ini menyebabkan ralat masa tamat (timeout) pada Leetcode.
Pendekatan 2: Kaedah Dioptimumkan (One Pass)
Anda boleh menyelesaikannya dalam satu laluan (one pass) menggunakan dua pemboleh ubah: minPrice dan maxProfit.
- Kompleksiti Masa: O(n)
- Kompleksiti Ruang: O(1)
Cara ia berfungsi:
- Tetapkan minPrice kepada Infinity.
- Tetapkan maxProfit kepada 0.
- Gelung melalui setiap harga.
- Jika harga semasa lebih rendah daripada minPrice, kemas kini minPrice.
- Jika harga semasa ditolak minPrice adalah lebih besar daripada maxProfit, kemas kini maxProfit.
Jejak contoh dengan harga [7, 1, 5, 3, 6, 4]:
- Hari 1: Harga 7. minPrice menjadi 7. maxProfit kekal 0.
- Hari 2: Harga 1. minPrice menjadi 1. maxProfit kekal 0.
- Hari 3: Harga 5. 5 - 1 = 4. maxProfit menjadi 4.
- Hari 4: Harga 3. 3 - 1 = 2. maxProfit kekal 4.
- Hari 5: Harga 6. 6 - 1 = 5. maxProfit menjadi 5.
- Hari 6: Harga 4. 4 - 1 = 3. maxProfit kekal 5.
Jawapan Akhir: 5.
Versi yang dioptimumkan lebih baik kerana ia hanya melihat setiap harga sekali sahaja. Ia boleh diskalakan dengan baik untuk set data yang besar.
Sumber: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1