貪心演算法應用#

買賣股票的最佳時機 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 天賣，結果一致。

fun maxProfit(prices: IntArray): Int {
    var totalProfit = 0
    for (i in 1 until prices.size) {
        if (prices[i] > prices[i - 1]) {
            // 只要今天比昨天高，就把價差吃下來
            totalProfit += prices[i] - prices[i - 1]
        }
    }
    return totalProfit
}

貪心的局限性#

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

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

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

延伸：股票系列問題#

買賣股票的最佳時機 II ^↗ 能用貪心是因為給了「上帝視角」且無交易成本。更複雜的變體需要動態規劃。

排程問題：先定義「優化指標」，再選貪心策略#

排程是貪心演算法最精華的應用場景之一，但它有一個很多人沒想清楚的前提。

假設只有一台機器，要依序做完一批任務。這裡有個關鍵觀察：不管你怎麼排，總工時都是固定的——所有任務的處理時間加起來就是那麼多，最後一個任務的完成時刻不會因為換順序而改變。

所以排程要優化的，從來不是「總時間」，而是某個更細緻的指標：是要讓「最晚交件的延遲」最小？還是讓「平均每個任務的等待時間」最短？不同的指標，對應到完全不同的最佳貪心策略。這正是貪心思維的核心：動手排之前，先想清楚到底要最佳化什麼。

指標 ↔️ 策略對應表#

幾個值得留意的地方：

• EDD 完全不在乎任務做多久，只在乎誰先到期。直覺上很合理——要讓最嚴重的遲交盡量不嚴重，當然先處理快到期的。
• Weighted SPT 排序的是「權重 ÷ 時間」，可以理解成每單位時間能消化掉多少重要性，也就是任務的「重要性密度」。密度高的先做，整體加權等待最小。
• Moore 演算法的巧思在於「反悔」：先樂觀地照截止時間塞進去，一旦發現某個任務塞不下了，就回頭把目前已排清單中最耗時的那個踢掉——犧牲一個換來後面好幾個能準時，逾期數因此最少。

直覺範例：為什麼 SPT 最佳#

假設有兩個案子：一個要做 4 天，一個要做 1 天。兩種排法的「總等待時間」（每個案子完成時刻的加總）：

差別一眼可見：先做大的，那個只要 1 天的小案被硬生生拖到第 5 天才完成。把短任務排前面，能讓它早早結束、不再累積等待——這就是 SPT 最佳的根本原因。

SPT 的實作其實就是一次排序：

// 任務以處理時間排序，回傳最小總完成時間
fun minTotalCompletionTime(processingTimes: IntArray): Long {
    val times = processingTimes.sorted()  // 短任務排前面，即 SPT

    var elapsed = 0L          // 目前累積的時刻
    var totalCompletion = 0L
    for (t in times) {
        elapsed += t                  // 這個任務的完成時刻
        totalCompletion += elapsed
    }
    return totalCompletion
}

這些貪心策略對各自的指標是「可證明最佳」，不是退而求其次的近似答案。EDD 給出的最大延遲、SPT 給出的總完成時間，都是理論上的最小值。

這點要和「貪心只能拿到近似解」的問題（見近似演算法與鬆弛）嚴格區分開：在那些問題裡貪心只是個堪用的捷徑，在排程這裡貪心就是正解。