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

LeetCode 121. Best Time to Buy and Sell Stock

給定數組 prices，第 i 個元素是第 i 天股票價格。只允許完成最多一筆交易（買入後賣出），求最大利潤。

問題分析

遍歷數組，維護到當前為止的最低價格 `minPrice`，第 i 天賣出的最大利潤為 `prices[i] - minPrice`。全局最大值即為答案。

算法流程

1. 初始化 `minPrice = prices[0]`, `maxProfit = 0`。
2. 從 i=1 遍歷到 n-1：
3. 更新 `maxProfit = max(maxProfit, prices[i] - minPrice)`。
4. 更新 `minPrice = min(minPrice, prices[i])`。
5. 返回 `maxProfit`。

代碼實現（C++）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0) return 0;
        int minPrice = prices[0];
        int maxProfit = 0;
        for(int i = 1; i < n; i++) {
            maxProfit = max(maxProfit, prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }
        return maxProfit;
    }
};

複雜度

• 時間：O(n)，單次遍歷。
• 空間：O(1)，常數額外空間。

變體延伸

• 多次交易 (II)：所有上升段落利潤相加。
• 含冷凍期 (III)：DP 狀態機。
• 含手續費 (IV)：DP 或貪心。
• 最多 k 筆交易 (IV)：DP O(nk) 或優化 O(n log n)。

總結

本題是股票系列的入門，核心思想是「維護歷史最小值，計算當前差值」，這是許多單遍歷優化問題的通用模式。