貪心演算法應用#

LeetCode 122：買賣股票的最佳時機 II#

題目規則#

給定股票每日價格陣列，求最大利潤。

• 持倉限制：同一時間最多持有 1 股
• 交易次數：無限制
• 手續費：無

解法比較#

貪心策略#

核心邏輯：只要明天的股價比今天高，就今天買、明天賣。

收集所有「上漲」的價差，就是最大總利潤。

數學證明#

將「長期波段利潤」拆解為「每日價差利潤」：

股價由 1 漲到 5：

• 長線操作：第 1 天買，第 5 天賣，利潤 = 4
• 貪心操作：(2-1) + (3-2) + (4-3) + (5-4) = 4

兩者數學等價！

案例分析#

案例一：[7, 1, 5, 3, 6, 4]

總利潤：7

案例二：[1, 2, 3, 4, 5]（連續上漲）

每日買賣：(2-1) + (3-2) + (4-3) + (5-4) = 4

等同於第 1 天買、第 5 天賣，結果一致。

def maxProfit(prices):
    total_profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            # 只要今天比昨天高，就把價差吃下來
            total_profit += prices[i] - prices[i-1]
    return total_profit

貪心的局限性#

此策略成立的前提是「無交易手續費」。

如果每筆交易都有手續費，這種頻繁買賣會導致虧損。真實股市中此策略完全不可行，因為：

1. 無法預知明天股價
2. 交易成本會侵蝕利潤

延伸：股票系列問題#

LeetCode 122 能用貪心是因為給了「上帝視角」且無交易成本。更複雜的變體需要動態規劃。