Thời Điểm Mua Bán Cổ Phiếu Tốt NhấtBest Time to Buy and Sell Stock
Hiểu bài
Cho mảng prices, prices[i] là giá cổ phiếu ngày thứ i.
- Bạn chỉ được mua một lần và bán một lần sau đó.
- Trả về lợi nhuận lớn nhất; nếu không thể có lời thì trả về 0.
prices = [7,1,5,3,6,4] → 5 // mua ngày giá 1, bán ngày giá 6
prices = [7,6,4,3,1] → 0 // giá chỉ giảm → không muaÝ chính: lướt một lần, luôn nhớ giá thấp nhất đã gặp (ngày mua tốt nhất tới hiện tại).
- Mỗi ngày thử bán: lời = giá hôm nay − giá thấp nhất.
- Đây là lựa chọn tốt-tại-chỗ kiểu tham lam (Greedy).
Xem cách cơ bản (chậm hơn)
O(n²) time, O(1) spacefunction maxProfitNaive(prices: number[]): number {
let best = 0
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
best = Math.max(best, prices[j] - prices[i]) // mua ngày i, bán ngày j
}
}
return best
}Cách này thử mọi cặp ngày mua-bán → hai vòng lồng nhau O(n²).
Chỉ cần nhớ giá thấp nhất tính tới hiện tại là đủ, giảm về một lần quét O(n).
Lời giải tối ưu
O(n) time, O(1) spacefunction maxProfit(prices: number[]): number {
let minPrice = Infinity
let maxProfit = 0
for (const price of prices) {
if (price < minPrice) {
minPrice = price // ngày mua tốt nhất tới hiện tại
} else if (price - minPrice > maxProfit) {
maxProfit = price - minPrice // bán hôm nay có lời hơn không?
}
}
return maxProfit
}Một lần quét, giữ hai biến: giá thấp nhất đã thấy và lợi nhuận lớn nhất.
- Tại mỗi ngày, hoặc cập nhật giá mua thấp hơn, hoặc thử chốt lời.
- Lựa chọn tham lam "mua ở đáy thấp nhất tới hiện tại" cho ra kết quả tối ưu mà không cần lưu bảng dp.
Chạy thử từng bước
- 1
price=7: 7 < Infinity → minPrice=7.
price:7minPrice:7maxProfit:0 - 2
price=1: 1 < 7 → minPrice=1.
price:1minPrice:1maxProfit:0 - 3
price=5: 5-1=4 > 0 → maxProfit=4.
price:5minPrice:1maxProfit:4 - 4
price=6: 6-1=5 > 4 → maxProfit=5.
(price=3,4 không vượt được).
price:6minPrice:1maxProfit:5 - 5
Hết mảng → trả về maxProfit=5.
result:5
Trường hợp biên phải nhớ
Mảng rỗng hoặc một ngày → không bán được → 0.
Giá giảm liên tục [7,6,4,3,1] → không lần nào có lời → 0.
Giá tăng liên tục → lời = giá cuối − giá đầu.
Giá thấp nhất nằm ở cuối → không kịp bán sau đó → vẫn dùng đáy trước đó.