901.股票价格跨度

题目描述：

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的跨度。

当日股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

数据范围：
$1\le n \le 10^4$

题解：

需要查询当前值的前一个比自己大的值的位置，如果是离线的，可以直接倒着使用单调减栈，变成了下一个最大问题。但是是在线的算法，也可以尝试使用单调减栈，跨度就是 $day - st.top()$ 。

代码：

class StockSpanner {
public:
    stack<pair<int, int>> st; // day, price
    int day = 0;
    StockSpanner() {
        st.push({0, 1e9});
    }
    
    int next(int price) {
        day++;
        while(st.size() && st.top().second <= price)
        {
            st.pop();
        }
        int ans = day - st.top().first;
        st.push({day, price});
        return ans;
    }
};