C++でのオンラインストックスパン

ある株の毎日の相場を収集し、その日のその株の価格のスパンを返すAPIがあるとします。ここで、今日の株価のスパンは次のように定義されます-

• 株価が今日の価格以下であった連続最大日数（今日から始まり、逆方向に戻る）。

たとえば、[100、80、60、70、60、75、85]のような7日間の株式シェアレコードが表示された場合、株式スパンは[1、1、1、2、1、4、6]になります。そのAPIの実際のモジュールを作成する必要があります。これは、このモジュールが呼び出されるときに使用されます

これを解決するには、次の手順に従います-

• 2つの配列st、v、counterを定義し、counterを0に設定します
• カウンターを1増やします
• stが空ではなく、価格> =v[スタックトップ要素]
  • スタックからポップします。
• ans：=スタックが空の場合はカウンター、それ以外の場合はans：=カウンター–スタックトップ
• 価格をvに挿入
• カウンターをstに挿入
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

#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;
}

入力

Initialize the class, then call next() method using different values. See the main() method

出力

1
1
1
2
1
4
6