057 · Online Stock Span

algorithm

Published

July 13, 2026

My First Thoughts

嗯，这道题题目有些绕，其实是在看当前价格相对于之前连续几天是不是一个局部高点。

也就是：

当前价格是多长时间以来的最高值？

这里的时间单位是天。

比如拿到当前值 val，需要怎么比较呢？

首先比较上一个价格。

如果当前值更大，或者至少不小于上一个价格，就继续往前看。

如果上一个价格已经比当前值更大，那就停下来，答案就是 1，因为只能算今天自己。

题目里写的是一个类：

StockSpanner()
next(price)

这个是面向对象的写法，我还不熟悉，我是这样理解的

如果我们已经有一个价格数组 prices，那能不能返回每一天的跨度数组？

比如：

prices = [100, 80, 60, 70, 60, 75, 85]

可以用计数和指针。

对每个位置 i，先把今天自己算进去：

span = 1

然后从前一天开始往前看：

j = i - 1

只要前面的价格小于或等于今天的价格，就说明这一整段还可以继续算进来：

while j >= 0 and prices[i] >= prices[j]:
    span += 1
    j -= 1

最后把这个 span 放进结果：

def stock_span(prices):
    results = []

    for i in range(len(prices)):
        span = 1
        j = i - 1

        while j >= 0 and prices[i] >= prices[j]:
            span += 1
            j -= 1

        results.append(span)

    return results

这个做法逻辑上应该是成立的。

如果输入是：

prices = [100, 80, 60, 70, 60, 75, 85]

返回就是：

[1, 1, 1, 2, 1, 4, 6]

所以如果题目给的是完整 list，这个写法已经能解出来。

Why That Is Not Enough

上面的 list 写法可以解出每一天的答案。

不过原题不是一次性给完整 list，而是每次调用 next(price)，只来一个新的价格，并且要立刻返回今天的跨度。

这只是接口形式的变化。我们依然可以在类里面保存之前见过的价格，然后每次来一个新价格，就往前扫。

比如暴力版可以这样写：

class StockSpanner:

    def __init__(self):
        self.prices = []

    def next(self, price):
        self.prices.append(price)

        span = 1
        j = len(self.prices) - 2

        while j >= 0 and price >= self.prices[j]:
            span += 1
            j -= 1

        return span

这也能得到正确答案。

所以暴力写法的问题不是思路错，而是重复工作太多。

它每次来了一个新价格，都从前一天开始，一天一天往前扫。

比如：

prices = [100, 80, 60, 70, 60, 75]

算 70 的时候，会看：

70 >= 60
70 < 80

所以 70 的跨度是 2。

这其实已经说明了一件事：

70 可以覆盖 [60, 70] 这一段，长度是 2

后面算 75 的时候，暴力写法又会重新一天一天看：

75 >= 60
75 >= 70
75 >= 60
75 < 80

这里就有重复。

因为之前算 70 的时候，我们已经知道 70 可以覆盖它前面的 60。现在既然：

75 >= 70

那么 75 不只可以覆盖 70 这一天，也一定可以覆盖 70 当时已经覆盖的那一整段。

所以不需要再单独检查那一天 60。

可以直接把 70 的跨度加到 75 的跨度里。

这就是关键优化：

如果当前价格能覆盖前面某一天，就可以直接加上那一天已经算好的跨度，跳过一整段。

Final Idea

我们不再只保存价格本身，而是保存一组信息：

(price, span)

其中：

price 是某一天的价格
span 是这一天自己已经算出来的跨度

用一个栈 stack 保存这些二元组。

当新价格 price 到来时，先认为今天至少能算自己：

span = 1

然后看栈顶。

如果栈顶价格小于或等于今天价格：

stack[-1][0] <= price

说明今天价格可以覆盖栈顶那一天。

而栈顶那一天不是只代表一天，它还带着自己的跨度：

old_price, old_span = stack.pop()
span += old_span

这一步的意思是：

当前价格吃掉了栈顶那一天，以及栈顶那一天之前已经能连续覆盖的整段。

然后继续看新的栈顶。

只要当前价格还能覆盖，就继续弹出并累加跨度。

直到遇到一个比当前价格更大的旧价格，就停下来。因为跨度要求的是连续天数，遇到更大的价格就不能再往前算了。

最后把今天自己的信息放回栈里：

stack.append((price, span))

然后返回 span。

用例子看：

prices = [100, 80, 60, 70, 60, 75, 85]

处理到 75 之前，栈里可以理解成：

[(100, 1), (80, 1), (70, 2), (60, 1)]

现在来了 75。

先有：

span = 1

栈顶是 (60, 1)：

75 >= 60
span += 1

继续看新的栈顶 (70, 2)：

75 >= 70
span += 2

继续看新的栈顶 (80, 1)：

75 < 80
停

所以 75 的跨度是：

1 + 1 + 2 = 4

这对应：

75, 60, 70, 60

然后把 (75, 4) 放进栈里。

Why It Works

栈里保存的是一些还可能挡住未来价格的天。

如果一个旧价格被当前价格覆盖了，那么它以后就不需要单独留在栈里了。

比如当前来了 75，它覆盖了 (70, 2)。

这说明：

75 >= 70

而 (70, 2) 的意思是：

70 已经可以覆盖自己和前面连续的一段，长度是 2

既然 75 比 70 还大，那么 75 当然也可以覆盖 70 覆盖的那整段。

所以可以直接：

span += old_span

而不是重新一天一天往前数。

栈里剩下来的价格，从底到顶是递减的。

因为所有小于或等于当前价格的旧价格都会被弹出。最后留在当前价格左边的第一个栈顶，一定是比当前价格更大的价格。

它正好就是跨度停止的地方。

每个价格最多入栈一次、出栈一次，所以整体效率就从反复往前扫，变成了线性级别。

Code

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price):
        span = 1

        while self.stack and self.stack[-1][0] <= price:
            old_price, old_span = self.stack.pop()
            span += old_span

        self.stack.append((price, span))

        return span

old_price 在代码里没有继续使用，但把它写出来可以让二元组的含义更清楚：

(old_price, old_span)

如果想写得更短，也可以这样：

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

Complexity

Time	\(O(1)\) amortized per `next` call - 单次调用里可能弹出多个元素，但每个价格最多入栈一次、出栈一次；如果总共调用 `n` 次，总时间是 \(O(n)\)
Space	\(O(n)\) - 最坏情况下价格一直下降，所有价格都会留在栈里

Takeaway

当暴力解法需要反复向前扫描，而且前面某个位置已经算出了一段连续长度时，可以考虑把“值”和“这段长度”一起保存。后面遇到更大的当前值时，直接累加这段长度，就能跳过重复检查。

← Quiz