【力扣】单调栈：901. 股票价格跨度

【力扣】单调栈：901. 股票价格跨度

1. 题目介绍

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

• 当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
• 例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

代码实现 StockSpanner 类：

• StockSpanner() 初始化类对象。

• int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。

• 示例：
  

2. 思路

调用 next 时，

• 输入是新的一天的股票价格，
• 需要返回包含此日在内的，往前数最多有连续多少日的股票价格是小于等于今日股票价格的个数。

如果把每日的 price 当成数组不同下标的值，即需要求出每个值与上一个更大元素之间的下标之差。这种题目可以用单调栈求解，具体原理如下：

• 单调栈是一种和单调队列类似的数据结构。
  • 单调队列主要用于解决滑动窗口问题，
  • 单调栈则主要用于解决NGE问题（Next Greater Element），也就是，对序列中每个元素，找到下一个比它大的元素。（当然，“下一个”可以换成“上一个”，“比它大”也可以换成“比他小”，原理不变。）
• 这比单调队列还简单一点。
  • 我们维护一个栈，表示“待确定NGE的元素”，然后遍历序列。
  • 当我们碰上一个新元素，我们知道，越靠近栈顶的元素离新元素位置越近。
  • 所以不断比较新元素与栈顶，如果新元素比栈顶大，则可断定新元素就是栈顶的NGE，于是弹出栈顶并继续比较。直到新元素不比栈顶大，再将新元素压入栈。显然，这样形成的栈是单调递减的。

此题的具体解法：
栈的元素可以是股票价格的下标（即天数）和股票价格的二元数对，并且在栈中先插入一个天数为 0 天，最大值作为价格的二元数对，来保证栈不会为空。调用 next 时，先将栈中价格小于等于此时 price 的元素都弹出，直到遇到一个大于 price 的值，并将 price 入栈，计算下标差返回。

3. 解题代码

class StockSpanner {
private:
    stack<pair<int, int>> stackp; 
    int ts;
public:
    StockSpanner() {
        this->stackp.emplace(0, INT_MAX);
        this->ts = 0;
    }
    int next(int price) {
        ts++;
        while (price >= stackp.top().second) {
            stackp.pop();	// 出栈
        }
        int res = ts - stackp.top().first;
        stackp.emplace(ts, price);	// 入栈
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

参考

【1】https://leetcode.cn/problems/online-stock-span/