Intuition#

追蹤到目前為止的最低買入價，每一天都計算「今天賣出能賺多少」來更新最大利潤。

• 如果我們在遍歷過程中記住「歷史最低價」，那每天的最大獲利就是 當天價格 - 歷史最低價
• 這本質上是一個滑動視窗問題：左邊界是最低價的位置，右邊界是當前位置

Approaches#

1: Brute Force#

• 概念: 嘗試所有 (買入, 賣出) 配對，找出最大利潤
• 時間複雜度: O(n²)
• 空間複雜度: O(1)

class Solution {
    fun maxProfit(prices: IntArray): Int {
        var maxProfit = 0
        for (i in prices.indices) {
            for (j in i + 1 until prices.size) {
                maxProfit = maxOf(maxProfit, prices[j] - prices[i])
            }
        }
        return maxProfit
    }
}

⭐2: One Pass (追蹤最低價)#

• 概念: 一次遍歷，持續追蹤最低買入價，並計算當前價格賣出的利潤
• 時間複雜度: O(n)
• 空間複雜度: O(1)

class Solution {
    fun maxProfit(prices: IntArray): Int {
        var minPrice = Int.MAX_VALUE
        var maxProfit = 0
        for (price in prices) {
            minPrice = minOf(minPrice, price)
            maxProfit = maxOf(maxProfit, price - minPrice)
        }
        return maxProfit
    }
}

🔑 Takeaways#

• Pattern: 追蹤前綴最小值 / 滑動視窗
• 關鍵技巧: 很多「找最大差值」的問題都可以轉化為追蹤歷史最小（或最大）值，避免巢狀迴圈