C++で解くオンライン株価スパン（Stock Span）問題

ある銘柄の毎日の株価を記録し、その日の「スパン」を返すAPIを考えてみましょう。ここでいう今日の株価のスパンとは、次のように定義されます。

• 今日から過去にさかのぼって、株価が今日の価格以下であった日が連続して何日続いたかという最大の日数。

例えば、7日間の株価データが [100, 80, 60, 70, 60, 75, 85] だった場合、それぞれの日のスパンは [1, 1, 1, 2, 1, 4, 6] となります。この記事では、このAPIの本体となるモジュールをC++で実装する方法を解説します。

単調スタックを使ったアプローチ

この問題は単調スタック（Monotonic Stack）を使うことで効率的に解けます。各呼び出し時に、現在の価格より小さい過去の価格情報だけをスタックに残すことで、不要な比較を省きます。

アルゴリズムの手順

1. 2つの配列 st（インデックス用スタック）と v（価格履歴）、およびカウンター counter を用意し、counter を0で初期化します。
2. next(price) が呼ばれたら、まず counter を1増やします。
3. スタックが空でなく、かつ price がスタックトップが指す価格以上である間、スタックから要素をポップし続けます。
4. スタックが空なら ans = counter、そうでなければ ans = counter - スタックトップの値 とします。
5. 現在の価格を v に追加し、counter を st にプッシュします。
6. ans を返します。

C++での実装例

以下のコードは、上記のアルゴリズムを実際に実装したものです。

#include <bits/stdc++.h>
using namespace std;
class StockSpanner {
   public:
   vector <int> st;
   int counter;
   vector <int> v;
   StockSpanner() {
      counter = 0;
   }
   int next(int price) {
      counter++;
      while(!st.empty() && price >= v[st.back() - 1])st.pop_back();
      int ans = st.empty() ? counter : counter - st.back();
      v.push_back(price);
      st.push_back(counter);
      return ans ;
   }
};
main(){
   StockSpanner ob;
   cout <<(ob.next(100)) << endl;
   cout <<(ob.next(80)) << endl;
   cout <<(ob.next(60)) << endl;
   cout <<(ob.next(70)) << endl;
   cout <<(ob.next(60)) << endl;
   cout <<(ob.next(75)) << endl;
   cout <<(ob.next(85)) << endl;
}

入力

クラスを初期化した後、main() メソッド内で異なる値を引数として next() メソッドを順に呼び出します。

出力

1
1
1
2
1
4
6

計算量について

一見すると next() の中でwhileループを回しているため計算量が心配になりますが、各価格はスタックにプッシュされ、高々1回しかポップされません。したがって、N回の呼び出し全体でO(N)、つまりならし計算量（Amortized Complexity）で1回あたりO(1)となり、非常に効率的な実装です。