LeetCode 901. 股票价格跨度

2024-04-11 HGNULB 约 9 分钟

文章信息 8 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 2-5 微软美团 LeetCode 75

题目描述

✅ 901. 股票价格跨度

题意分析

这是一道数据流上的设计题：价格一天一天地喂进来，每次调用 next(price) 都要立刻返回「包括今天在内，往前连续有多少天的价格小于等于今天」。注意是「小于等于」，等于也算在跨度里，这个细节直接决定后面比较符是否带等号。

关键约束是在线：不能先把所有价格收集齐再统一处理，每次调用必须马上给出答案。这排除了任何需要看到未来数据的做法。

调用次数上限一万量级，看起来每次现场往回扫也能过，但这类题真正想考的是「均摊 $O(1)$」。约束里「价格范围有限、调用次数很多」的组合，加上答案本身是「向左延伸到第一个更大的价格为止」这种表述，提示应该在结构里保留一部分历史，让每个历史价格最多被处理常数次。

边界上要考虑：第一次调用没有历史，答案必然是 1；价格全程递减时每次答案都是 1；价格全程递增时第 k 次调用的答案是 k，此时结构会被清空到只剩一个元素。

解法：单调栈维护候选

核心思路

暴力做法是把所有历史价格存进一个数组，每次调用从当前位置往左逐个比较，直到遇到比今天大的价格就停。最坏情况（价格全程不增）每次都要扫到头，总代价 $O(n^2)$。

瓶颈在哪里？在于同一批历史价格被反复检查。假设昨天的价格是 80、今天是 100，那么昨天左边那些比 80 小的价格，今天必然也比 100 小——昨天已经确认过一次，今天又从头确认一遍，做的是完全重复的工作。

由此得到核心观察：一个价格一旦被某个更大（或相等）的后来者「吞掉」，它就永远不可能再成为任何未来查询的边界。因为未来的价格若能越过它，必然也能越过那个更大的后来者。所以它可以被彻底丢弃，但它贡献的天数不能丢，要合并进吞掉它的那个价格里。

于是维护这样一个不变量：结构中自底向上保存若干二元组 (price, span)，price 严格单调递减，且每个二元组的 span 表示「以该 price 为终点、向左延伸到上一个更大价格为止的天数」。这些 span 加起来恰好等于至今为止的总天数，不重不漏——这正是能直接累加求答案的原因。

处理新价格 cur 时：把栈顶所有 price <= cur 的二元组弹出，它们代表的那些天全部落在 cur 的跨度范围内，把它们的 span 累加到 cur 的 span 上；弹不动时说明栈顶价格严格大于 cur，跨度到此为止。最后把 (cur, span) 压回去，单调递减的不变量继续成立。

解题步骤

选择保存二元组而不是单个价格。这是本题与普通单调栈最大的区别：如果只存价格，弹出时只知道「弹掉了几个二元组」，而不知道它们各自代表多少天，答案会算少。存 span 相当于把被压缩掉的历史长度随身携带。

span 初始化为 1。今天自己必然算进跨度里，这一天不来自任何弹出操作，所以必须先记上。

循环条件用 <= 而不是 <。题目说的是「小于或等于今天价格的连续天数」，价格相等的历史日也应该被计入，因此相等时同样要弹出合并。写成 < 会让相等的那天留在栈里，成为假的边界。

每弹出一个就把它的 span 加到当前 span 上，而不是简单地 span++。被弹出的二元组可能已经压缩了很多天，只加 1 会严重少算。

循环结束后把 (price, span) 压入栈，并返回 span。压栈是为了让今天成为未来查询的候选；返回值就是刚累加完的 span，不需要再遍历栈求和。

以调用序列 next(100), next(80), next(60), next(70), next(60), next(75), next(85) 走一遍。

next(100)：栈空，span = 1，压入 (100, 1)，返回 1。栈：[(100,1)]。

next(80)：栈顶 100 > 80，不弹，span = 1，压入 (80, 1)，返回 1。栈：[(100,1), (80,1)]。

next(60)：栈顶 80 > 60，不弹，span = 1，返回 1。栈：[(100,1), (80,1), (60,1)]。

next(70)：栈顶 (60,1) 满足 60 <= 70，弹出，span = 1 + 1 = 2；新栈顶 80 > 70，停止。压入 (70, 2)，返回 2。栈：[(100,1), (80,1), (70,2)]。注意 60 那一天已经被 70 吸收，以后再也不会单独出现。

next(60)：栈顶 70 > 60，不弹，span = 1，返回 1。栈：[(100,1), (80,1), (70,2), (60,1)]。

next(75)：弹出 (60,1)，span = 2；再看栈顶 (70,2) 满足 70 <= 75，弹出，span = 2 + 2 = 4；新栈顶 80 > 75，停止。压入 (75, 4)，返回 4。栈：[(100,1), (80,1), (75,4)]。这个 4 覆盖的正是 60、70、60、75 这四天，验证了 span 的合并语义。

next(85)：弹出 (75,4)，span = 5；弹出 (80,1)，span = 6；栈顶 100 > 85，停止。压入 (85, 6)，返回 6。栈：[(100,1), (85,6)]。手工核对：85 往左依次是 75、60、70、60、80，全部小于等于 85，加上自己共 6 天，再往左是 100 大于 85，正好截断。

代码实现

// 新价格到来时，弹出所有 price <= current 的元素并累加跨度。
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;
    }
}

// 新价格到来时，弹出所有 price <= current 的元素并累加跨度。
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
}

复杂度分析

时间复杂度：单次调用均摊 $O(1)$，n 次调用总计 $O(n)$。凭什么？每个价格一生只会入栈一次、出栈一次，出栈之后就被合并进别人的 span 里永不复现；虽然某一次调用可能连续弹出很多元素（如例中的 next(85)），但弹出的总次数被入栈总次数 n 严格限制住，摊到每次调用就是常数。

空间复杂度：$O(n)$。凭什么？栈里保存的是当前仍可能成为未来边界的价格，最坏情况是价格严格递减（如 100、99、98……），此时没有任何元素被弹出，栈会一直增长到 n 个二元组。

关键点总结

把「重复扫描的历史」压缩成一个带权候选：当一段历史对未来的影响可以用一个代表元加一个数量概括时，就该把它合并掉。这是单调结构从 $O(n^2)$ 降到均摊 $O(n)$ 的通用理由，不局限于本题。

存权重而非只存元素：普通「下一个更大元素」只需存下标，靠下标差算距离；本题是流式的、没有全局下标，所以改成随元素携带 span。遇到在线场景先问自己「我还能不能拿到下标」，答案是否定时就要把信息塞进栈元素里。

比较符的等号来自题面而非习惯：「小于或等于」对应弹栈条件 <=，维持的是严格递减栈；如果题面写「严格小于」，就要改成 < 并维持非严格递减栈。写代码前先把这句话对应清楚。

不变量要能一句话说清：「栈内价格自底向上严格递减，各 span 之和等于已处理天数」。面试时说出这句，等价于证明了算法正确性，比逐行讲代码有效得多。

均摊分析要主动讲：面试官问复杂度时，如果只答「$O(1)$」容易被追问「可是里面有 while 循环」。标准答法是「单次最坏 $O(n)$，但每个元素只进出栈各一次，所以均摊 $O(1)$」。

面试视角：这题常被用来检验候选人能否把离线的「下一个更大元素」迁移到在线场景。答完后可以主动补一句：若还要支持撤销最近一次调用，则需要额外记录每次弹出了哪些元素，栈就要换成可持久化结构。

易错点总结

错误写法：弹栈时写 span++ 而不是 span += 弹出的 span。用例 100, 80, 60, 70, 75 → 在 next(75) 时应弹出 (60,1) 和 (70,2) 得到 4，写成 span++ 只会得到 1 + 1 + 1 = 3，返回值少算了被 70 提前吸收的那一天。

错误写法：弹栈条件用 < 而不是 <=。用例 next(70), next(70) → 第二次调用时栈顶价格 70 不满足 70 < 70，不弹出，返回 1；正确答案是 2，因为等于今天价格的那天也计入跨度。

错误写法：把 span = 1 写在 while 循环之后或初始化为 0。用例 next(100) → 栈为空循环一次都不执行，span 保持 0，第一次调用就返回 0，而任何一天的跨度至少是 1（自己）。

错误写法：压栈时压入的是原始 span 1 而不是累加后的 span。用例 100, 60, 70, 75 → next(70) 返回 2 但压入 (70,1)，随后 next(75) 弹出 (70,1) 与 (60,1) 得到 3，正确答案是 4；被吞掉的天数在栈里丢失，错误会一直向后传染。

错误写法：只在栈非空时才压栈，或者忘记压栈。用例连续调用 next(50) 三次 → 若第一次因为栈空而没压入，第二次仍看到空栈返回 1，第三次也返回 1，正确答案应是 1、2、3。每次调用都必须压栈，无一例外。

错误写法：Java 里用 Stack 并混用 push 与 add。Stack 继承自 Vector，add 是尾部追加而 push 也是尾部，但 Deque 的 push 是头部插入、add 是尾部追加，两者语义相反。用例 100, 80, 60 下若在 ArrayDeque 上误用 add 压栈却用 peek 取栈顶，会取到最早的 100 而不是最新的 60，弹栈条件全盘失效。统一用 push/pop/peek 三件套。

错误写法：Go 里弹栈时先截断切片再读取被弹元素。写成 s.stack = s.stack[:len(s.stack)-1] 之后再访问 s.stack[len(s.stack)-1][1]，读到的是新栈顶而非刚弹出的元素，用例 100, 60, 70 下 next(70) 会把 100 的 span 累加进去，返回 2 但把 100 误当成已消费，后续所有答案偏移。必须先取值后截断。

错误写法：把栈声明为结构体值字段并在值接收者方法里修改。Go 中 func (s StockSpanner) Next(...) 对 s.stack 的 append 不会写回原对象，用例任意连续调用都会永远返回 1。必须用指针接收者 func (s *StockSpanner) Next(...)。

错误写法：每次调用都重新遍历整个栈求和来算答案。用例价格严格递减 10^4 次 → 栈长度线性增长，每次都全扫一遍变成 $O(n^2)$ 约五千万次操作，在数据流题的调用量下会超时；答案就是累加得到的 span 本身，不需要二次遍历。

相似题目

题目	难度	考察点
739. 每日温度	中等	离线且要找右侧更大元素，栈里存下标靠差值算距离，无需携带权重
496. 下一个更大元素 I	简单	需要先对第二个数组预处理再用哈希映射回查询数组，多一层索引转换
503. 下一个更大元素 II	中等	数组循环，靠遍历两遍取模模拟环形，考察边界的重复扫描处理
84. 柱状图中最大的矩形	困难	弹栈时要同时确定左右两侧边界并结算面积，比单纯计数复杂一层
42. 接雨水	困难	弹栈结算的是凹槽体积，需要栈顶、次栈顶与当前元素三者共同参与计算