স্টক প্রাইস স্ট্রিম দেওয়া। প্রতিদিনের স্প্যান = আজকের প্রাইস থেকে পिछে ঠিক কতদিন ধরে প্রাইস <= আজকের প্রাইস।
উদাহরণ: [100,80,60,70,60,75,85] → স্প্যান: [1,1,1,2,1,4,6]।
সমাধানের ধাপসমূহ
- মনোটোনিক স্ট্যাক (ডিক্রিজিং প্রাইস) রাখুন।
- প্রতিটি নতুন প্রাইসের জন্য: স্ট্যাক টপ >= করেন্ট প্রাইস হলে পপ করুন।
- স্প্যান = করেন্ট ডে - স্ট্যাক টপের ডে (স্ট্যাক খালি হলে করেন্ট ডে)।
- করেন্ট (ডে, প্রাইস) পুশ করুন।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class StockSpanner {
vector<int> st; // stores day indices
vector<int> prices;
int day = 0;
public:
StockSpanner() {}
int next(int price) {
day++;
while (!st.empty() && price >= prices[st.back() - 1]) st.pop_back();
int span = st.empty() ? day : day - st.back();
prices.push_back(price);
st.push_back(day);
return span;
}
};
int main() {
StockSpanner ob;
cout << ob.next(100) << endl; // 1
cout << ob.next(80) << endl; // 1
cout << ob.next(60) << endl; // 1
cout << ob.next(70) << endl; // 2
cout << ob.next(60) << endl; // 1
cout << ob.next(75) << endl; // 4
cout << ob.next(85) << endl; // 6
}
ইনপুট
Initialize the class, then call next() method using different values. See the main() method
আউটপুট
1 1 1 2 1 4 6
