Stock Span Problem
各日の株価の終値が与えられます。prices[i] は i 日目の価格です。i 日目のスパンとは、i 日目を含み、i 日目で終わる連続した日数のうち、価格が prices[i] 以下である日数です。
prices と同じ順序で、各日のスパンを返してください。各日のスパンは少なくとも 1 です。日数には常にその日自身が含まれるためです。
関数
- pricesinteger-array
- 各日の価格を順番に
- 戻り値integer-array
- 各日の範囲を、同じ順序で
制約
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- それ以前の日の価格が同じ場合もスパンに含まれます。スパンを止めるのは、価格が厳密に高い場合だけです。
例
- 入力
- prices = [31, 27, 14, 21, 30, 18, 40]
- 出力
- [1, 1, 1, 2, 4, 1, 7]
- 説明
- 21の3日目は14を超えてさかのぼり、27で止まります：幅は2。30の4日目は31で止まります：幅は4。40の6日目はそれ以前のすべての価格を上回り、7日間すべてをカバーします。
- 入力
- prices = [8, 8, 3, 8]
- 出力
- [1, 2, 1, 4]
- 説明
- 価格が等しい場合も数えるため、8である1日目は0日目を含み、2を得ます。8である3日目は、3日目自身とそれ以前の2つの8を含み、期間は4です。
- 入力
- prices = [50, 40, 30, 20]
- 出力
- [1, 1, 1, 1]
- 説明
- 毎日、前日より安くなるため、どの期間もその日より前にはさかのぼらず、すべての期間は1です。
発展問題
価格が1つずつ届くようになり、価格が届くたびに各スパンを報告しなければなりません。それでも機能する方法はどれで、呼び出しの間に何を保持しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
毎日、後ろ向きに数えるのは作業の繰り返しです。同じ価格が8000日続く場合、最後の日だけで8000日分さかのぼることになります。今日からさかのぼるとき、どの過去の日をもう調べずに済ませられるでしょうか？
今日の価格が以前の日の価格以上になった時点で、その以前の日が後の区間を止めることはもうありません。今日はその日より近く、価格も同じかそれ以上だからです。その後の日すべてより高い価格の日だけが引き続き重要であり、それらの価格は古い日から新しい日へと下がっていきます。
- 日付を順番に進み、まだ重要な過去の日付をインデックスとしてスタックに保持します。今日の答えを出す前に、価格が今日の価格以下である日をすべてスタックから取り出します。スタックが空なら、期間は0日目までさかのぼります。そうでなければ、期間はスタックの一番上に残った日の翌日で終わります。その後、今日をプッシュします。
解説
ある日のスパンは、価格が厳密に高い最も近い過去の日で終わります。その日を見つけるためにさかのぼると、1日あたり最大 n ステップかかります。代わりに、将来のスパンの境界になりうる日だけを残しておきましょう。価格が厳密に降順になるインデックスのスタックを使えば、1回の走査ですべての境界を見つけられます。
毎日、逆向きに数える
正しいが、最大のテストでは終わらない
考え方
定義に従います。日 iについて、そこにある価格が prices[i]以下である間、一度に1日ずつさかのぼります。日 iも数えます。最初に現れる厳密に高い価格、または配列の先頭で、連続区間は終了します。
どの走査も、以前の走査結果を再利用しません。価格が横ばいまたは上昇している場合、各走査は日0までさかのぼります。n = 10^4日なら、約 5 × 10^7ステップになります。
アルゴリズム
pricesと同じ長さの配列spanを作成します。- 各日
iについて、カウンターを0に設定し、ポインターjをiに設定します。 j ≥ 0かつprices[j] ≤ prices[i]の間、カウンターに1を加え、jを1日前に移動します。- カウンターを
span[i]に格納します。最終日の後、spanを返します。
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return spanより気温の高い日を求める単調スタック
考え方
最も近い、それより前の日のうち価格が厳密に高い日をブロッカーと呼びます。スパンはtoday - blockerです。該当する日がない場合はtoday + 1です。
最初の例では、3日目の価格は21で、4日目の価格は30です。それ以降のどの探索も最初に4日目に到達し、30を超える価格は21も超えるため、3日目が再びブロッカーになることはありません。一般に、今日の日が来たとき、それ以前の候補のうち価格が今日の価格以下のものはすべて役目を終えています。それらを取り除きます。スタックの一番上に残った日が、今日のブロッカーです。その後、今日の日を追加します。
スタック内の価格は下から上に向かって厳密に小さくなるため、最後まで残った最初の日が最も近い高値の日です。最初の例では、4日目は3日目と1日目を取り除き、0日目で止まるため、スパンは4 - 0 = 4です。各日は1回だけ追加され、取り除かれるのも最大1回なので、この処理はO(n)で実行されます。
アルゴリズム
span配列と、日数インデックス用の空のスタックを作成します。- 各日
todayについて、価格がprices[today]以下であるインデックスをスタックから取り出します。 - スタックが空なら、スパンは
today + 1です。そうでなければ、todayからスタックの先頭にあるインデックスを引きます。 todayをスタックに追加し、次の日に進みます。spanを返します。
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
落とし穴と境界ケース
<=ではなく<でポップすること。[8, 8, 3, 8]では、最後の日のスパンは4です。先に現れる8で止めると2になります。- スタックが空のときに
today + 1ではなくtodayと書くこと。0日目の値は0ではなく1でなければなりません。 - 1日につき1回だけポップすること。最初の例では、40は5日目、4日目、0日目を処理する必要があります。5日目の後で止めると、4日目がブロッカーのように見え、スパンは7ではなく2になります。
- LuaとRでは、配列のインデックスは1から始まります。1始まりのインデックスでは、スタックが空のときのスパンは
today + 1ではなくtodayです。
よくある質問4
株式スパン問題の時間計算量はどのくらいですか？
単調スタックを使うと、各日がスタックから取り出されるのは最大1回なので、時間計算量はO(n)、追加の空間計算量はO(n)です。価格が上がり続けるか横ばいの場合、各日から逆方向にたどる方法の時間計算量はO(n²)です。
スタックには価格と日数のどちらを格納すべきでしょうか？
日付のインデックス。期間は日数であり、それが分かるのはブロッカーのインデックスだけです。prices[index]で価格を読み取り、比較に使います。
株価スパン問題は、別個のスタックを使わずに解けますか？
はい。j = today - 1から始め、j ≥ 0かつprices[j] ≤ prices[today]の間は、j - span[j]へジャンプします。そのスパン内の各日の価格はprices[j]以下だからです。スパンはtoday - jです。ジャンプ先はスタックに残る日のみなので、パスの計算量はO(n)のままです。
株価スパン問題は、直前のより大きい要素を求める問題ですか？
はい、日数で測ります。各日について、価格が厳密に高い最も近い過去の日を見つけ、何日前かを報告します。走査方向または比較を反転させると、同じスタックで次に大きい値、次に小さい値、または前にある小さい値を求められます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def stockSpan(prices):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
prices = [31, 27, 14, 21, 30, 18, 40]
期待される出力
[1, 1, 1, 2, 4, 1, 7]