LeetCode 121. Best Time to Buy and Sell Stock：單次交易最大利潤

問題描述

給定每日股價數組，僅允許一次買入一次賣出（買在賣前），求最大利潤。無利潤返回 0。
例：[2,4,6,1,3,8,3] → 在 1 買入、8 賣出，利潤 7。

一維掃描貪心解法

維護歷史最低價 min_price，遍歷每日價格計算當前賣出利潤，更新最大利潤：

class Solution:
    def maxProfit(self, prices):
        if len(prices) < 2: return 0
        min_price = prices[0]
        max_profit = 0
        for price in prices:
            if price < min_price:
                min_price = price
            elif price - min_price > max_profit:
                max_profit = price - min_price
        return max_profit

C++ 實現

int maxProfit(vector& prices) {
    int min_price = INT_MAX, max_profit = 0;
    for (int price : prices) {
        min_price = min(min_price, price);
        max_profit = max(max_profit, price - min_price);
    }
    return max_profit;
}

複雜度與正確性

• 時間：O(n)，單次遍歷
• 空間：O(1)，常數變量
• 貪心證明：最優解必在歷史最低點買入，因更早買入成本更低或相同

變體延伸

若允許多次交易（LeetCode 122）：累加所有上漲段利潤。
若限制交易次數 k（LeetCode 188）：DP dp[k][i] 表示前 i 天最多 k 筆交易最大利潤。