LeetCode 901. 股票价格跨度——单调栈在线处理数据流

适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约20分钟 | 难度：中等

---

开篇故事

前两篇讲的都是离线算法——数组数据全都在，一次性处理完。但现实工程中，更多的场景是数据流：数据一条一条进来，每进来一条都要立刻给出答案。

这道股票价格跨度就是这种场景。每天收盘价一个一个进来，我不知道未来的价格，只知道历史的。面试官最喜欢考这类在线设计题，因为它不仅考算法，还考你对「状态设计」的理解。

我见过不少同学，离线单调栈题一写就过，但换成设计题，脑子就卡住了，不知道把单调栈的状态存哪里。这篇文章就把这个思维跨越讲清楚。

---

一、题目解析

题目描述：

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

当日股票价格的跨度被定义为该股票价格小于或等于今日价格的最大连续日数（从今日算起，向前计算）。

示例：

输入：["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
     [[], [100], [80], [60], [70], [60], [75], [85]]
输出：[null, 1, 1, 1, 2, 1, 4, 6]

解释：

• 第1天：100，之前没有数据，跨度=1
• 第2天：80<100，跨度=1
• 第3天：60<80，跨度=1
• 第4天：70>60，60那天也<=70，跨度=2（第3、4天）
• 第5天：60<70，跨度=1
• 第6天：75>60，往前看：60<=75，70<=75，所以跨度=4（第3、4、5、6天）
• 第7天：85>75，75、60、70、60、80都<=85，跨度=6

关键理解： 「跨度」就是从今天往前，连续多少天的价格都 <= 今天的价格（包括今天本身）。

---

二、解法一：暴力记录历史价格

思路分析

最直接的思路：把所有历史价格存下来，每次 next(price) 调用时，从最新价格往前扫，直到遇到比 price 大的价格为止。

class StockSpanner {
    private List<Integer> prices;
    
    public StockSpanner() {
        prices = new ArrayList<>();
    }
    
    public int next(int price) {
        prices.add(price);
        int span = 1;
        // 从倒数第二个价格往前扫
        for (int i = prices.size() - 2; i >= 0; i--) {
            if (prices.get(i) <= price) {
                span++;
            } else {
                break; // 遇到更大的价格，停止
            }
        }
        return span;
    }
}

复杂度分析

• 时间复杂度：每次 next 调用 O(n)。n 是历史价格数量，最坏情况扫描所有历史。
• 空间复杂度：O(n)。

---

三、解法二：动态规划预计算跨度

思路分析

可以利用已有的跨度信息来加速查找。对于当前价格 price，如果前一天的跨度是 span，说明前一天及其往前 span-1 天的价格都 <= 前一天的价格。如果 price >= 前一天价格，我们可以直接跳过前一天的整个跨度范围。

这本质上是一种「跳跃」优化，和解法二思路相似，但写法稍有不同：

class StockSpanner {
    private List<Integer> prices;
    private List<Integer> spans;
    
    public StockSpanner() {
        prices = new ArrayList<>();
        spans = new ArrayList<>();
    }
    
    public int next(int price) {
        int span = 1;
        int i = prices.size() - 1;
        // 利用已存储的跨度进行跳跃
        while (i >= 0 && prices.get(i) <= price) {
            span += spans.get(i); // 跳过整个span范围
            i -= spans.get(i);   // 直接跳到span起点的前一天
        }
        prices.add(price);
        spans.add(span);
        return span;
    }
}

复杂度分析

• 时间复杂度：均摊 O(1)。每个价格点最多被「跳过」一次，均摊下来是常数时间。
• 空间复杂度：O(n)。

---

四、解法三（最优）：单调栈存 (价格, 跨度) 对

核心思想

这是最优雅、最地道的解法。把上面动态规划的思想，用单调栈来实现。

单调栈里存的不是单纯的价格或下标，而是 (价格, 跨度) 的配对。维护单调递减栈（价格从栈底到栈顶递减）。

每次新价格进来：

1. 弹出所有 价格 <= 新价格 的栈顶，累加它们的跨度
2. 把 (新价格, 累加跨度+1) 压栈

这样单调栈里只保留了「关键节点」——那些在未来某天来看，可能成为「拦截点」的价格。被弹出的价格，说明它们已经被新价格覆盖，跨度信息已经合并进来了。

完整代码

import java.util.*;

class StockSpanner {
    // 单调递减栈，存 (价格, 跨度) 对
    // 用两个栈分别存，或者用 int[] 表示
    private Deque<int[]> stack; // int[0]=price, int[1]=span
    
    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;
    }
}

手动模拟

以调用序列 [100, 80, 60, 70, 60, 75, 85] 为例：

调用	price	弹出操作	栈状态 (价格,跨度)	返回span
next(100)	100	无	[(100,1)]	1
next(80)	80	无(80<100)	[(100,1),(80,1)]	1
next(60)	60	无(60<80)	[(100,1),(80,1),(60,1)]	1
next(70)	70	弹(60,1),span=1+1=2	[(100,1),(80,1),(70,2)]	2
next(60)	60	无(60<70)	[(100,1),(80,1),(70,2),(60,1)]	1
next(75)	75	弹(60,1)span=2,弹(70,2)span=4	[(100,1),(80,1),(75,4)]	4
next(85)	85	弹(75,4)span=5,弹(80,1)span=6	[(100,1),(85,6)]	6

最终结果：[1,1,1,2,1,4,6]，正确！

复杂度分析

• 时间复杂度：均摊 O(1)。每个元素最多入栈一次、出栈一次，n次调用总共 2n 次操作，均摊每次 O(1)。
• 空间复杂度：O(n)。最坏情况（单调递减序列）所有元素都在栈中。

---

五、举一反三

在线单调栈的通用设计模式

这道题展示了一个重要的设计模式：在线处理 + 单调栈。把单调栈封装成一个类的状态，每次处理一个新数据，立即返回结果。

// 通用在线单调栈框架
class OnlineMonotonicStack {
    private Deque<int[]> stack; // [value, accumulated_info]
    
    public OnlineMonotonicStack() {
        stack = new ArrayDeque<>();
    }
    
    public int process(int value) {
        int accumulatedInfo = 1; // 初始信息
        
        // 弹出满足条件的元素，合并信息
        while (!stack.isEmpty() && condition(stack.peek()[0], value)) {
            accumulatedInfo += stack.pop()[1]; // 合并
        }
        
        stack.push(new int[]{value, accumulatedInfo});
        return accumulatedInfo;
    }
    
    private boolean condition(int stackTop, int current) {
        return stackTop <= current; // 根据题意调整
    }
}

类似设计题

题目	变体
239. 滑动窗口最大值	在线 + 单调队列（deque）
155. 最小栈	在线 + 辅助栈维护最小值
295. 数据流的中位数	在线 + 双堆维护中位数

---

六、踩坑实录

坑一：存 (价格, 跨度) 时，跨度是 span 不是 1

刚开始我犯了个错误：把所有元素都以跨度=1压栈，心想反正每次弹出时可以查历史重新算。结果每次都要往前扫，回到了 O(n) 的复杂度。

单调栈的精髓就是把合并后的跨度存进去，让信息随着合并而增长。每次弹出时，直接累加弹出元素的跨度，不需要重新查历史。

// 错误：存跨度1
stack.push(new int[]{price, 1}); // 每次存1，信息没有压缩

// 正确：存合并后的跨度
stack.push(new int[]{price, span}); // span已经包含了被弹出元素的跨度

坑二：判断条件是 <= 还是 <

跨度的定义是「小于或等于今日价格的最大连续日数」，注意是小于等于。所以弹出条件是 栈顶价格 <= 当前价格，而不是严格小于。

如果写成 <，那么和今天价格相等的历史天就不会被计入跨度，答案偏小。

// 正确：<=
while (!stack.isEmpty() && stack.peek()[0] <= price) {
    span += stack.pop()[1];
}

// 错误：<，相等的天没被计入
while (!stack.isEmpty() && stack.peek()[0] < price) {
    ...
}

坑三：忘记把初始 span 设为 1

每次调用至少包含今天本身，所以 span 初始值是 1，而不是 0。然后每弹出一个历史节点，加上它的跨度。

int span = 1; // 今天本身算1天
// 弹出并累加...

如果初始设为 0，答案会少 1，整体偏小一天。

---

七、总结

这道题的价值在于展示了单调栈从「离线批处理」到「在线流式处理」的迁移思路。

核心设计思路：

1. 单调栈存 (价格, 跨度) 对而不是单纯的值
2. 新元素来时弹出所有被覆盖的节点，累加跨度
3. 把合并后的信息压回栈，保持单调性

这种「在栈里存聚合信息」的模式在很多在线设计题里都很有用，遇到「连续窗口」「滑动统计」等场景，都值得尝试。