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.
ts
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)
Cách cơ bản
O(n²) time, O(1) spacets
function 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
}Vì sao cách này chậm:
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
Tối ưu
O(n) time, O(1) spacets
function 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ấu chốt:
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
Chạy thử qua từng bước — bấm vào một bước để xem dòng code tương ứng
1function maxProfit(prices: number[]): number {2let minPrice = Infinity3let maxProfit = 04for (const price of prices) {6if (price < minPrice) {7minPrice = price // ngày mua tốt nhất tới hiện tại8} else if (price - minPrice > maxProfit) {9maxProfit = price - minPrice // bán hôm nay có lời hơn không?10}11}12return maxProfit14}
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 đó.