Best Time to Buy and Sell Stock

Bài toán

Cho một mảng prices trong đó prices[i] là giá của một cổ phiếu vào ngày thứ i. Bạn chỉ được phép hoàn thành một giao dịch (mua một lần và bán một lần). Hãy trả về lợi nhuận tối đa có thể đạt được. Nếu không thể có lãi, trả về 0.

Ví dụ:

Input: prices = [7,1,5,3,6,4]
Output: 5
Giải thích: Mua ngày 2 (giá 1) và bán ngày 5 (giá 6). Lãi 6-1=5.
(Lưu ý: Không được bán ngày 1 (giá 7) rồi mua ngày 2 (giá 1)).

Phân Tích & Tiếp Cận

Cách 1: Brute Force

Với mỗi ngày i (ngày mua), duyệt các ngày j > i (ngày bán) để tìm max profit. $O(n^2)$.

Cách 2: One Pass (Sliding Window / Two Pointers)

Thực chất ta cần tìm cặp (buy, sell) sao cho sell - buy lớn nhất và buy xuất hiện trước sell. Điều này tương đương với việc: Tại mỗi ngày sell (giá hiện tại), ta muốn biết giá thấp nhất lịch sử trước đó để trừ đi.

Thuật toán: Duyệt qua từng ngày giá (price):

1. Nếu price < minPrice: Cập nhật minPrice mới (đây là điểm đáy tiềm năng để mua).
2. Nếu price > minPrice: Tính thử lợi nhuận (price - minPrice) và so sánh với maxProfit.

function maxProfit(prices: number[]): number {
    let minPrice = Infinity;
    let maxProfit = 0;

    for (const price of prices) {
        if (price < minPrice) {
            minPrice = price; // Tìm thấy giá mua tốt hơn
        } else {
            const currentProfit = price - minPrice;
            maxProfit = Math.max(maxProfit, currentProfit);
        }
    }

    return maxProfit;
}

• Time Complexity: $O(n)$ - Duyệt 1 vòng.
• Space Complexity: $O(1)$.

Góc nhìn Sliding Window

Dù cách trên trông giống Greedy, nó cũng là dạng đơn giản nhất của Sliding Window:

• Cửa sổ biến thiên [L, R]. L là ngày mua (giá min), R là ngày bán hiện tại.
• Khi prices[R] < prices[L]: Điều đó có nghĩa ta đã tìm thấy đáy mới thấp hơn cả điểm mua cũ. Ta trượt hẳn cửa sổ: Gán L = R. (Bắt đầu chu kỳ mua mới từ đáy này).