Leetcode 150 | Day 5: 最適な株の売買タイミング
Leetcode 121では、株を売買する最適なタイミングを見つける問題が出題されます。価格の配列が与えられ、各インデックスは「日」を表し、その値はその日の「価格」を表します。
目標はシンプルです。ある日に買い、それより後の日に売ることで、最大の利益を得ることです。利益が出せない場合は、0を返します。
制約事項:
- 配列の長さは最大100,000。
- 価格は最大10,000。
- 売却は購入後に行う必要があります。
アプローチ1: 素朴な方法 (Brute Force)
力任せ探索（Brute Force）では、考えられるすべての「買い」と「売り」の組み合わせをチェックします。これには2重ループを使用します。
- 時間計算量: O(n²)
- 問題点: 処理が遅すぎます。
もし日が1,000日あれば、1,000,000回のチェックが発生します。もし100,000日あれば、10,000,000,000回のチェックが必要になります。これにより、Leetcodeではタイムアウトが発生します。
アプローチ2: 最適化された方法 (One Pass)
minPrice と maxProfit という2つの変数を使うことで、1回の走査（One Pass）で解くことができます。
- 時間計算量: O(n)
- 空間計算量: O(1)
仕組み:
minPriceを無限大（Infinity）に設定する。maxProfitを0に設定する。- 各価格を順番に見ていく。
- 現在の価格が
minPriceより低ければ、minPriceを更新する。 - 「現在の価格 -
minPrice」がmaxProfitより大きければ、maxProfitを更新する。
価格 [7, 1, 5, 3, 6, 4] の場合のトレース例:
- 1日目: 価格 7。
minPriceは 7 になり、maxProfitは 0 のまま。 - 2日目: 価格 1。
minPriceは 1 になり、maxProfitは 0 のまま。 - 3日目: 価格 5。5 - 1 = 4。
maxProfitは 4 になる。 - 4日目: 価格 3。3 - 1 = 2。
maxProfitは 4 のまま。 - 5日目: 価格 6。6 - 1 = 5。
maxProfitは 5 になる。 - 6日目: 価格 4。4 - 1 = 3。
maxProfitは 5 のまま。
最終的な答え: 5.
最適化されたバージョンが優れている理由は、各価格を一度しか確認しないためです。大規模なデータセットに対しても効率的に動作します。
Source: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1