901. 股票价格跨度
题目描述
设计类 StockSpanner，逐日接收某支股票的价格，并返回当日的价格跨度。
某一天的价格跨度定义为：从这一天开始往前数，股价都小于或等于当天股价的连续天数的最大值，当天本身也算在内。
StockSpanner()：初始化对象。
next(price)：传入今天的股价 price，返回今天的价格跨度。
示例 1
输入：操作 = ["StockSpanner","next","next","next","next","next","next","next"] 参数 = [[],[100],[80],[60],[70],[60],[75],[85]] 输出：[null,1,1,1,2,1,4,6]
解释：例如第六天价格 75，往前连续的 60、70、60 和自己都不超过 75，跨度为 4；第七天 85 的跨度为 6。
数据范围
1 <= price <= 10^5next最多被调用10^4次。
解题思路
维护一个单调栈，栈里存 (价格, 跨度)，价格从栈底到栈顶严格递减。新价格到来时，把栈顶所有价格不超过它的元素弹出，并把它们的跨度累加到自己身上：被弹出的那一段天数都比今天便宜，以后也不会再成为别人的“挡板”，因为今天的价格更高、更靠后。最后把 (price, span) 压栈。
为什么正确
栈中价格严格递减；每个元素的 span 等于它“吃掉”的连续天数，栈中所有 span 之和等于已处理的天数。
复杂度分析
每天最多入栈一次、出栈一次，均摊时间 O(1)，空间 O(n)。
易错点
比较条件是“小于或等于”，相等的价格也要弹出；弹出时要加上对方的 span，而不是只加 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
span = 1
while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1]
self.stack.append((price, span))
return spanclass StockSpanner {
private Deque<int[]> stack;
public StockSpanner() {
stack = new ArrayDeque<>();
}
public int next(int price) {
int span = 1;
while (!stack.isEmpty() && stack.peek()[0] <= price) {
span += stack.pop()[1];
}
stack.push(new int[]{price, span});
return span;
}
}class StockSpanner {
public:
vector<pair<int, int>> stk;
StockSpanner() {
stk.clear();
}
int next(int price) {
int span = 1;
while (!stk.empty() && stk.back().first <= price) {
span += stk.back().second;
stk.pop_back();
}
stk.push_back({price, span});
return span;
}
};type StockSpanner struct {
stack [][2]int
}
func Constructor() StockSpanner {
return StockSpanner{stack: [][2]int{}}
}
func (this *StockSpanner) Next(price int) int {
span := 1
for len(this.stack) > 0 && this.stack[len(this.stack)-1][0] <= price {
span += this.stack[len(this.stack)-1][1]
this.stack = this.stack[:len(this.stack)-1]
}
this.stack = append(this.stack, [2]int{price, span})
return span
}var StockSpanner = function() {
this.stack = [];
};
StockSpanner.prototype.next = function(price) {
let span = 1;
while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) {
span += this.stack.pop()[1];
}
this.stack.push([price, span]);
return span;
};class StockSpanner {
stack: number[][];
constructor() {
this.stack = [];
}
next(price: number): number {
let span = 1;
while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) {
span += this.stack.pop()![1];
}
this.stack.push([price, span]);
return span;
}
}