給定一個整數陣列
prices，其中prices[i]代表第i天的股票價格。你只能選擇某一天買入，並在之後的某一天賣出，求最大利潤。如果無法獲利則回傳0。
Example:
Input: prices = [7,1,5,3,6,4] Output: 5
Intuition
TIP
追蹤到目前為止的最低買入價，每一天都計算「今天賣出能賺多少」來更新最大利潤。
- 如果我們在遍歷過程中記住「歷史最低價」，那每天的最大獲利就是
當天價格 - 歷史最低價 - 這本質上是一個滑動視窗問題：左邊界是最低價的位置，右邊界是當前位置
Approaches
1. Brute Force — O(n²) / O(1)
- Idea: 嘗試所有 (買入, 賣出) 配對，找出最大利潤
- Time:
O(n²) - Space:
O(1)
Brute Force Code
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 (track min price) — O(n) / O(1)
- Idea: 一次遍歷，持續追蹤最低買入價，並計算當前價格賣出的利潤
- Time:
O(n) - Space:
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: 追蹤前綴最小值 / 滑動視窗
- Key trick: 很多「找最大差值」的問題都可以轉化為追蹤歷史最小（或最大）值，避免巢狀迴圈