股票价格跨度 图解题解

这道题到底在问什么

依次喂入

100,80,60,70,60,75,85

依次返回

1,1,1,2,1,4,6

看 75

60,70,60,75 这 4 天都 ≤ 75 → 跨度 4

先想最直接的笨办法

以最后一天 85 为例。暴力做法要从它左边的 75 开始,一格一格往左看,这一步就可能扫很多格。（动画第 4 步）

最优解：一步一步想明白

1. 3先想最直白的:对每天的价格,从今天往左回头数,只要左边的价 ≤ 今天就继续数,一碰到更大的就停。我们先体会一下这样为什么慢。
2. 4从 85 往左一个个数以最后一天 85 为例。暴力做法要从它左边的 75 开始,一格一格往左看,这一步就可能扫很多格。
3. 575 ≤ 85 ✓ 继续75 ≤ 85,算进去,接着看更左边的 60。每一个都要亲自比一次。
4. 660 ≤ 85 ✓ 继续60 也 ≤ 85,继续。最坏情况下(价格一直递减再来个最大值),这要一路扫到最左边,单次就 O(n)。
5. 7瓶颈在「每天都从头回扫」。其实那些被矮价跨过的天,以后永远不会再单独用到——它们已经被某个更高的价「吃掉」了。这就引出单调栈。
6. 8关键想法:栈里从底到顶价格严格递减。新价来了,凡是 ≤ 它的栈顶都被它「盖住」——弹出,并把这些天的跨度加到自己头上(它们能数到的,我也能数到)。
7. 9准备喂入 100,80,60,70,60,75,85上面一排是即将依次喂入的股价,下面是栈(存 价·跨度 对)。开始时栈是空的,逐天处理。
8. 10栈空 → 跨度 = 1第一天 100,栈是空的,没人能往回数,跨度 = 1。把 100·1 压栈(价 100、跨度 1)。
9. 11栈顶 100 > 80 → 不弹80 来了。栈顶 100 > 80,挡住了,不能弹。所以往回只数到自己,跨度 = 1,压入 80·1。
10. 12栈顶 80 > 60 → 不弹60 来了。栈顶 80 > 60,挡住,不弹。跨度 = 1,压入 60·1。栈里价格从底到顶是 100,80,60,正好递减。
11. 13先看栈顶 6070 来了,跨度先记作 1(自己)。看栈顶 60 ≤ 70——它被 70 盖住了,要弹出,并把它的跨度加过来。
12. 14跨度 1 + 1 = 2弹出 60·1,把它的跨度 1 累加过来,现在 70 的跨度变 2。再看新栈顶 80。
13. 1580 挡住 → 停,压入 70·2新栈顶 80 > 70,挡住了,停止弹出。跨度 = 2,压入 70·2。注意 70 把刚才那个 60「吃」进了自己的跨度里。
14. 16栈顶 70 > 60 → 不弹又来个 60。栈顶 70 > 60,挡住,不弹。跨度 = 1,压入 60·1。
15. 17跨度从 1 起,看栈顶 6075 来了,跨度先记 1。栈顶 60 ≤ 75,被盖住,要弹。
16. 18跨度 1 + 1 = 2弹出 60·1,跨度累加成 2。再看新栈顶 70 ≤ 75——也被盖住,而 70 自己跨度是 2(早把那个 60 吃了),弹它要一次把 2 加过来。
17. 19跨度 2 + 2 = 4弹出 70·2,把它的跨度 2 加过来,现在 75 的跨度是 4。这一下就把「60、70、60」三天连同自己一起数清了——不用再回头逐格扫。
18. 2080 挡住 → 停,压入 75·4新栈顶 80 > 75,挡住,停。跨度 = 4,压入 75·4。这正是题面里 75 那天的答案。
19. 21跨度从 1 起,看栈顶 75最后一天 85,跨度先记 1。栈顶 75 ≤ 85,被盖住,要弹。
20. 22跨度 1 + 4 = 5弹出 75·4,一次把 4 加过来,跨度变 5。再看新栈顶 80 ≤ 85,也被盖住,继续弹。
21. 23跨度 5 + 1 = 6弹出 80·1,跨度累加到 6。再看新栈顶 100。
22. 24100 挡住 → 停,压入 85·6新栈顶 100 > 85,终于挡住了,停。跨度 = 6,压入 85·6。除了第一天的 100,前面 6 天都 ≤ 85。
23. 25返回序列 1,1,1,2,1,4,6 ✓把七天的跨度并排看:1,1,1,2,1,4,6,和题面完全一致。栈里最后只剩 100 和 85——它们是「还可能挡住未来」的两座高峰。
24. 26虽然某一次 next 可能弹很多个(像 85 弹了 2 个、75 弹了 2 个),但弹出去就再也不回来。一生只进出一次,把总功摊到每次调用就是常数。
25. 30若栈顶 == 当前价就不弹 → 跨度漏数假设连续两天都是 50。若条件写成「栈顶 < 当前价才弹」,第二天的 50 弹不动第一天的 50,跨度错成 1;正确用 ≤ 时会弹出,跨度应为 2。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class StockSpanner:
    def __init__(self):
        self.stack = []           # 每项 (价格, 跨度)
    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]   # 弹出并累加跨度
        self.stack.append((price, span))
        return span

class StockSpanner {
    stack<pair<int,int>> st;   // (price, span)
public:
    StockSpanner() {}
    int next(int price) {
        int span = 1;
        while (!st.empty() && st.top().first <= price) {
            span += st.top().second; st.pop();
        }
        st.push({price, span});
        return span;
    }
};

class StockSpanner {
    private Deque<int[]> st = new ArrayDeque<>();  // {price, span}
    public StockSpanner() {}
    public int next(int price) {
        int span = 1;
        while (!st.isEmpty() && st.peek()[0] <= price) {
            span += st.pop()[1];
        }
        st.push(new int[]{price, span});
        return span;
    }
}

复杂度

面试官可能追问