Best Time to Buy and Sell Stock
リスト prices が与えられます。ここで、prices[i] は i 日目の株価です。ある日に株を1株買い、後の日に売ることができます。得られる最大の利益を返してください。すべての取引で損失が発生する場合は、0 を返してください。
関数
- pricesinteger-array
- 各日の株価を順番に
- 戻り値integer
- 1回の購入とその後の売却で得られる最大利益、または0
制約
1 ≤ prices.length ≤ 1050 ≤ prices[i] ≤ 104- 取引は最大1回まで行い、購入した日より後の日に売却します。
例
- 入力
- prices = [7, 2, 5, 9, 1, 4]
- 出力
- 7
- 説明
- 1日目に2で買い、3日目に9で売ると、利益は7です。最安値の1は4日目で、9の後になるため、その後に売って得られる最大の利益は3だけです。
- 入力
- prices = [9, 7, 4, 3, 1]
- 出力
- 0
- 説明
- 価格は毎日下がるため、どの売却価格も購入価格を下回ります。取引は行わず、利益は0です。
発展問題
一度に保有できる株が最大1株で、好きなだけ取引できるとしたらどうでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
売却は必ず購入の後に行われます。売却日を選びましょう。その日に最も利益が出るのは、どの購入日でしょうか？
ある売却日に対して最適な購入日は、その日より前で最も価格が安い日です。先へ進みながらその日を覚えておけば、毎回改めて探す必要はありません。
日々を順番にたどり、これまでの最安値とこれまでの最高利益の2つの数値を記録します。毎日、その日の価格から最安値を引いた値と最高利益を比較し、その後、最安値を更新します。
解説
売る前に買わなければならないので、答えは最高価格から最低価格を引いたものではありません。売却できる日ごとに、最適な購入日はそれより前で最も安い日です。日付を順に見ていきながら、その最安価格を保持することで、問題を1回の走査で解けます。
すべての買いと売りのペアを試す
正しいが、最大のテストでは終わらない
考え方
すべての取引は、ある日の買いと、それより後の日の売りの組み合わせなので、すべてのペアを試して最大の差を保持します。最良の利益を 0 から始めることで、取引しない選択肢も考慮できます。許可されている取引はすべてチェックされるため、答えは正しいです。
n 個の価格のリストには、およそ n²/2 個のペアがあります。100,000 日なら、およそ 50 億回の引き算が必要です。
アルゴリズム
bestを0に設定します。- すべての購入日
buyを順に処理します。 - それぞれについて、その後のすべての売却日
sellを順に処理します。 prices[sell]からprices[buy]を引き、その値が大きければbestに保存します。bestを返します。
def maxProfit(prices):
best = 0
n = len(prices)
for buy in range(n):
for sell in range(buy + 1, n):
best = max(best, prices[sell] - prices[buy])
return best
これまでで最も安い価格で1回パス
考え方
売却日 i を固定します。最適な購入日は i までで最も安い日なので、日 i に売却する最適な取引で得られる利益は、prices[i] からそれまでの最低価格を引いたものです。各売却日には最適な購入日が対応するため、それらの利益の最大値が答えです。その日の価格が新たな最安値なら、利益は 0 で、取引しない場合と同じです。
この処理では各価格を一度ずつ読み込み、lowest と best の 2 つの数値を保持します。時間計算量は O(n)、空間計算量は O(1) です。
アルゴリズム
lowestを最初の価格に設定し、bestを0に設定します。- 価格を順番に確認します。
- 現在の価格が
lowestより低ければ、それを新しいlowestにします。 - 現在の価格から
lowestを引き、その値がbestより大きければ、bestに保存します。 bestを返します。
def maxProfit(prices):
lowest = prices[0]
best = 0
for price in prices:
if price < lowest:
lowest = price
elif price - lowest > best:
best = price - lowest
return best
落とし穴と境界ケース
- 最高価格から最低価格を引いた値を返す。
[7, 2, 5, 9, 1, 4]では8になるが、1は9の後にある。答えは7。 - 答えが負の値になることを許してしまう。
[9, 7, 4, 3, 1]では最良の差は-1。bestは最初の差ではなく、0から始める。 lowestを0から始める。その場合、すべての利益が価格そのものになり、[9, 7, 4, 3, 1]は9を返す。最初の価格から始める。
よくある質問3
Best Time to Buy and Sell Stock の時間計算量はどれくらいですか？
1回の走査による解法は、n 日間に対して O(n) 時間かかります。各価格を1回ずつ読み取り、追加の領域は O(1) です。これには、これまでの最低価格と最大の利益が含まれます。すべての日のペアを試すと、O(n²) 時間かかります。
最高価格から最低価格を引いてみてはどうでしょうか？
最安値は最高値の後に来ることがあり、売る前に買わなければなりません。[7, 2, 5, 9, 1, 4]では、1は9の後に来るため、許される最良の取引は2で買って9で売ることで、利益は7です。
Best Time to Buy and Sell Stock は動的計画法の問題ですか？
どちらの見方でも考えられます。これまでの最安値は毎日更新する小さな状態で、これは動的計画法の見方です。各売却を、それより前の日の中で最も安い日に対応させるのが、貪欲法の見方です。どちらの見方でも、1回の走査で処理する同じコードにたどり着きます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def maxProfit(prices):
# ここにコードを記述してくださいテスト #1
テスト #2
引数
prices = [7, 2, 5, 9, 1, 4]
期待される出力
7