LeetCode 901. 股票价格跨度
题目描述
题意分析
每次
next(price)输入当天价格，返回从今天向前连续多少天的价格都不高于今天，今天也计入跨度。遇到第一天严格更高的价格就必须停止，不能越过它继续统计。对象会连续接收价格，需要保留之前调用形成的状态。
解法：单调栈维护候选
核心思路
[!blue]
栈中每项记录
(price, span)，代表一段连续历史：price是这段最后一天的价格，也是段内最大价格，span是天数。各段按时间先后相接、不重叠，栈中价格从底到顶严格递减。新价格到来时先计入今天，令
span = 1。若栈顶价格不高于今天，该段内每一天也都不高于今天，而且这段紧挨着当前已统计的日期，所以可以整段弹出，把它的跨度全部加上。不断重复，直到栈空或遇到更高价格。停下时，更高的栈顶价格对应已合并区间之前的那一天，正是不能跨过的边界；栈空则说明全部历史都可纳入。将今天与被弹出的连续块合并为新块压栈，所得跨度就是答案，同时重新保持严格递减的栈序。
被合并块不必单独保存：未来价格若低于今天，会被今天挡住，无法到达这些旧日期；若不低于今天，则能一次吸收今天这块连同其中全部历史。因此压缩不会影响后续查询。
解题步骤
- 栈作为对象成员保留，各次调用共用；当天跨度初始化为 1。
- 当栈非空且栈顶价格
<= price时，弹出栈顶，将其保存的整段跨度累加到span。- 循环结束后压入
(price, span)，返回span。- 第一次调用返回 1；连续相同价格也会合并，因为题目允许历史价格等于今天。
代码实现
class StockSpanner {
private final Deque<int[]> 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;
}
}
type StockSpanner struct {
stack [][2]int
}
func Constructor() StockSpanner {
return StockSpanner{stack: make([][2]int, 0)}
}
func (s *StockSpanner) Next(price int) int {
span := 1
for len(s.stack) > 0 && s.stack[len(s.stack)-1][0] <= price {
// 栈顶已经代表连续多天，合并整块跨度。
span += s.stack[len(s.stack)-1][1]
s.stack = s.stack[:len(s.stack)-1]
}
// 将当天与被合并的历史压缩成一个新块。
s.stack = append(s.stack, [2]int{
price,
span,
})
return span
}
复杂度分析
设已经调用
next共n次。
- 时间复杂度：单次最坏 $O(n)$，均摊 $O(1)$。每一天只形成一次新栈项，之后最多被弹出一次，因此
n次调用的总工作量为 $O(n)$。- 空间复杂度：$O(n)$。价格持续下降时没有块能被合并，所有栈项都会保留。
关键点总结
[!green]
- 栈项记录的是整段天数，弹出时累加其跨度，而不只是增加一天。
- 每次合并的都是与今天相连的历史，连续性由栈顶顺序保证。
- 只有严格更高的价格才是边界，所以价格相等时也要弹栈。
易错点总结
[!yellow]
- 每次弹栈只加 1，会丢掉栈项已经压缩的历史天数。
- 不能每次调用都重新创建栈，否则无法根据之前价格计算跨度。
- 今天自身必须计入，初始跨度应为 1，不能从零开始。
- Go 使用指针接收者，才能把弹栈和压栈后的切片长度保存在同一个对象中。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 739. 每日温度 | 中等 | 同样寻找最近的更大元素边界，本题向左看历史并合并跨度，原题向右看未来并返回等待天数。 |
| 84. 柱状图中最大的矩形 | 困难 | 同样弹出不再构成有效边界的栈项，本题还能把被弹项已经覆盖的连续天数一并累计。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！