leetcode 901. 股票价格跨度

题目描述

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

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

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

示例：

输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

提示：

调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
每个测试用例最多可以调用 10000 次 StockSpanner.next。
在所有测试用例中，最多调用 150000 次 StockSpanner.next。
此问题的总时间限制减少了 50%。

题解——单调栈详解——快速获取最近的更大元素

理解题意

事实上，我们就是接收一个数组，代表股票价格，然后返回每个值左边连续小于等于它的数组长度+1(自身)。如果采用暴力，是O(N^2)的，不可接受。使用单调栈，可以在O(N)内解决。

转变思路

我们由求左边连续小于等于它的数组长度，转而求它左边从右往左第一个大于它的位置。知道了这个位置，那么它们之间的数不就都是小于等于这个数了吗。而单调栈的作用，可以使我们快速地找到第一个大于它的位置。

具体操作

我们维护一个单调递减栈，里面保存下标(也可以理解为哪一天)以及价格。考虑新加入的一天，如果大于等于栈顶，我们就不断地弹出栈顶，直到栈顶比price大或者栈为空，这样，栈顶就是最近的更高价格的位置。依次可以求得中间天数，返回即可。同时，要将新加入的这天入栈。

举个例子

这么说还是有些抽象，我们通过一个例子看一下。
就拿题目例子来说吧，我们对[100, 80, 60, 70, 60, 75, 85]进行查询。

遇到100，由于栈为空，左边没有小于等于它的，返回1，同时将{1,100}入栈。
遇到80，栈顶为100，比它大，说明左边仍然没有小于等于它的，返回1，将{2,80}入栈。
60同理，返回1，将{3,60}入栈。
遇到70，发现栈顶小了，{2,60}出栈，栈顶变为80，比它大了，说明最近的更高价格为第2天，那么中间的第三天就是比它小的，返回1+1=2，将{4,70}入栈。
遇到60，发现70比它大，返回1，将{5,60}入栈。
遇到75，将60，70出栈，栈顶变为{2,80}，说明最近的更高价格为第2天，中间的3、4、5都比它小，返回3+1=4，将{6,75}入栈。这里要注意，栈里虽然已经没有{2,60}了，但我们仍然会将它算进去，这是因为已经确定它比右边的70小了，如果70出栈，说明当前数肯定比它大，可以看作它隐性地出栈了，这也是为什么我们不是统计出栈的元素个数，而是寻找第一个大于它的位置，因为更小的元素可能没有了，但是更大是只会变得更近的。
遇到85，将75，80出栈，栈顶变为{1,100}，返回5+1=6，将{7,85}入栈，查询结束。

最终的查询结果就是[1,1,1,2,1,4,6]

代码

class StockSpanner {
    stack<pair<int,int>> stk;//单调递减栈
    int now=0;//记录当前天数
public:
    StockSpanner() {}
    
    int next(int price) {
        ++now;
        while(!stk.empty()&&stk.top().second<=price)//如果栈顶<=price，一直出栈
            stk.pop();
        int res=now-(stk.empty()?0:stk.top().first);//最终栈顶位置就是最近的更大位置,减去得到答案
        stk.push({now,price});//新的一天入栈
        return res;
    }
};