𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗡𝗴𝗮̀𝘆 𝟱: 𝗧𝗵𝗼̛̀𝗶 𝗶𝗺 𝘁𝗼̂́𝘁 𝗻𝗵𝗮̂́𝘁 đ𝗲̂̉ 𝗺𝘂𝗮 𝘃𝗮̀ 𝗯𝗮̀𝗻 𝗰𝗼̂̉ 𝗽𝗵𝗶𝗲̂́𝘂

Leetcode 121 yêu cầu bạn tìm thời điểm tốt nhất để mua và bán một cổ phiếu. Bạn nhận được một mảng các mức giá. Mỗi chỉ số đại diện cho một ngày. Giá trị là chi phí vào ngày đó.

Mục tiêu rất đơn giản. Mua vào một ngày và bán vào một ngày trong tương lai để đạt được lợi nhuận cao nhất. Nếu không thể có lợi nhuận, hãy trả về 0.

Các ràng buộc của bài toán:

  • Độ dài mảng lên đến 100.000.
  • Giá lên đến 10.000.
  • Bạn phải bán sau khi mua.

Cách 1: Phương pháp ngây thơ (Vét cạn - Brute Force)

Cách vét cạn kiểm tra mọi cặp mua và bán duy nhất. Cách này sử dụng hai vòng lặp.

  • Độ phức tạp thời gian: O(n²)
  • Vấn đề: Nó quá chậm.

Nếu bạn có 1.000 ngày, bạn thực hiện 1.000.000 lần kiểm tra. Nếu bạn có 100.000 ngày, bạn thực hiện 10.000.000.000 lần kiểm tra. Điều này gây ra lỗi quá thời gian (timeout) trên Leetcode.

Cách 2: Phương pháp tối ưu (Duyệt một lần - One Pass)

Bạn có thể giải quyết bài toán này chỉ trong một lần duyệt bằng cách sử dụng hai biến: minPrice và maxProfit.

  • Độ phức tạp thời gian: O(n)
  • Độ phức tạp không gian: O(1)

Cách hoạt động:

  1. Đặt minPrice là vô cực (Infinity).
  2. Đặt maxProfit là 0.
  3. Duyệt qua từng mức giá.
  4. Nếu giá hiện tại thấp hơn minPrice, hãy cập nhật minPrice.
  5. Nếu giá hiện tại trừ đi minPrice lớn hơn maxProfit, hãy cập nhật maxProfit.

Ví dụ mô phỏng với mảng giá [7, 1, 5, 3, 6, 4]:

  • Ngày 1: Giá 7. minPrice trở thành 7. maxProfit vẫn là 0.
  • Ngày 2: Giá 1. minPrice trở thành 1. maxProfit vẫn là 0.
  • Ngày 3: Giá 5. 5 - 1 = 4. maxProfit trở thành 4.
  • Ngày 4: Giá 3. 3 - 1 = 2. maxProfit vẫn là 4.
  • Ngày 5: Giá 6. 6 - 1 = 5. maxProfit trở thành 5.
  • Ngày 6: Giá 4. 4 - 1 = 3. maxProfit vẫn là 5.

Kết quả cuối cùng: 5.

Phiên bản tối ưu chiến thắng vì nó chỉ xem xét mỗi mức giá một lần. Nó có khả năng mở rộng tốt cho các tập dữ liệu lớn.

Nguồn: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1