37. Best Time to Buy and Sell Stock
読了目安 約1分
DP / LeetCode 121 (Easy) — 1 回の売買の最大利益。最安値を更新しながら 1 パスで走査する。
この章の目次
問題
LeetCode 121. Best Time to Buy and Sell Stock（Easy / カテゴリ: DP）
prices[i] は i 日目の株価です。
1 回だけ買い、その後の日に 1 回だけ売るときの最大利益を返してください。
利益が出る取引がなければ 0 を返します。
考え方
ヒント 1
「その日に売る場合の最大利益」は「その日の価格 − それまでの最安値」です。 状態として「i 日目までの最安値」と「i 日目までの最大利益」の 2 つを持ちます。
ヒント 2
遷移は minPrice = min(minPrice, prices[i]) と best = max(best, prices[i] - minPrice) の 2 行です。
初期条件は minPrice = prices[0]、best = 0。
左から 1 パス走査するだけで解けます。
Swift 実装のポイント
- 買う日と売る日の二重ループは O(N²) になります。最安値の更新に置き換えて O(N) にします。
bestの初期値 0 が「取引しない」という選択に対応します。- 同じ日の
min更新をmax更新より先に行っても、その日の利益が 0 になるだけで答えは変わりません。
模範解答
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
var minPrice = prices[0]
var best = 0
for p in prices {
minPrice = min(minPrice, p)
best = max(best, p - minPrice)
}
return best
}
}計算量: O(N)。