901. 股票价格跨度
设计一个算法收集某些股票的每日报价,并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数(从今天开始往回数,包括今天)。
实现 StockSpanner 类:
示例:
class StockSpanner {
public:
StockSpanner() {
this->stk.emplace(-1, INT_MAX);
this->idx = -1;
}
int next(int price) {
idx++;
while (price >= stk.top().second) {
stk.pop();
}
int ret = idx - stk.top().first;
stk.emplace(idx, price);
return ret;
}
private:
stack<pair<int, int>> stk;
int idx;
};
(1) 单调栈