---
title: "901. Online Stock Span"
url: "https://laigary.com/interview/coding/901-online-stock-span"
type: "note"
section: "coding"
date: "2025-04-02"
updated: "2026-07-28"
tags: ["Design", "Stack", "Monotonic"]
---

# 901. Online Stock Span

[901\. Online Stock Span](https://leetcode.com/problems/online-stock-span/)

每次餵進一個當日股價，回答「從今天往回數，**連續**有幾天的股價**小於等於**今天」。今天自己也算一天。

這個題目真的算是非常難，沒有寫過的話面試真的很難有機會寫出來。

## 思路

它是 [739. Daily Temperatures](/interview/coding/739-daily-temperatures) 的鏡像 —— 739 往右找第一個更高的，這題往左數連續有幾天不比今天高。但有一個關鍵差異：

**這題是 online 的。** 資料一次來一個，看不到未來，而且答案必須當場回傳。739 可以選正向或反向掃，這題直接沒得選：只能由左往右，而且只能靠「過去」的資訊。

### 暴力解與它浪費在哪

最直覺的做法是把所有價格存成一個陣列，每次呼叫往回掃到第一個更高的價格 —— 單次 $O(n)$，$n$ 次呼叫就是 $O(n^2)$。

浪費在哪？看這條丟棄規則：

> 如果今天的價格 `>=` 昨天的，那**昨天從此不必再單獨存在** —— 未來任何一天只要跨得過今天，就一定也跨得過昨天。

所以昨天可以被今天吸收掉。**但不能直接丟掉**，因為昨天代表的天數還算數 —— 它會被算進未來某一天的 span 裡。

### 最難的一步：想到要記錄天數

我卡最久的地方不是「該用單調棧」，而是**想到棧裡要多存一個天數**。

看到「往回數連續幾天」很自然就只想去存價格，然後就卡住了 —— 因為 pop 掉之後那幾天就消失了。但被吞掉的日子雖然不必再單獨比較，它們**還要被算進未來某一天的 span 裡**。

真正的關鍵認知是這一句：

**pop 掉的東西不能就這樣消失，它帶著資訊。**

想通之後，剩下的只是選一個載體來保存那個資訊 —— 把天數累加起來，或是記住位置之後再相減。兩種寫法下面都有。

### 棧裡存的不是價格，是「壓平的區間」

把被吞掉的天數**併進今天**，這就是解法的全部：

```python
count = 1                                   # 今天自己
while 棧頂價格 <= 今天:
    count += 棧頂的天數                       # 把它的天數接收過來
    pop
push([今天的價格, count])
```

棧裡的每一項代表**一段已經被壓平的區間**：`price` 是那一段的最高價（也就是那段最後一天的價格），`count` 是那一段涵蓋幾天。由底到頂，價格嚴格遞減。

739 存索引是為了算距離；這題把天數累加起來，連索引都不用維護。

### 等號的方向跟 739 相反

739 要的是**嚴格更高**才算答案；這題的 span 定義包含「小於**或等於**」，所以相等的價格要被吞掉。

```python
while self.prices and self.prices[-1][0] <= price:      # 901：<= 要吞
while stack and temperatures[i] > temperatures[stack[-1]]:  # 739：> 才結算
```

兩題放在一起看的時候，等號特別容易記反。可靠的做法是每次都回到題目定義去推，而不是背 code。

## 解題方向

### 寫法一：累加天數

```python
class StockSpanner:

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

    def next(self, price: int) -> int:
        count = 1
        while self.prices and self.prices[-1][0] <= price:
            prev = self.prices.pop()
            count += prev[1]
        self.prices.append([price, count])

        return count

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
```

拿官方的 `[100, 80, 60, 70, 60, 75, 85]` 跑一次，棧的變化把整個想法說得很清楚：

```text
next(100) → 1    [[100,1]]
next( 80) → 1    [[100,1], [80,1]]
next( 60) → 1    [[100,1], [80,1], [60,1]]
next( 70) → 2    [[100,1], [80,1], [70,2]]        吞掉 60
next( 60) → 1    [[100,1], [80,1], [70,2], [60,1]]
next( 75) → 4    [[100,1], [80,1], [75,4]]        吞掉 60 和 70，天數 1+1+2 = 4
next( 85) → 6    [[100,1], [85,6]]                吞掉 75 和 80，天數 1+4+1 = 6
```

看 `next(75)` 那一步：它一口氣吃掉 `[60,1]` 和 `[70,2]`，`count` 從 1 累加成 4。**那個 `[70,2]` 裡的 2 就是它當初從 60 接收過來的**，所以歷史天數是層層傳遞下去的，不會漏也不會重複算。

最後 `[100,1]` 從頭到尾沒被動過 —— 100 是整段期間的最高價，沒有人跨得過它。

### 寫法二：記錄索引

另一個載體是位置。自己維護一個呼叫次數 `i`，棧裡放 `(價格, 索引)`；彈完之後棧頂就是「左邊第一個比今天貴的那天」，兩個索引相減就是 span。

```python
class StockSpanner:

    def __init__(self):
        self.stack = []          # (price, index)
        self.i = -1

    def next(self, price: int) -> int:
        self.i += 1
        while self.stack and self.stack[-1][0] <= price:
            self.stack.pop()

        if not self.stack:
            # 左邊沒有人比今天貴，從第 0 天到今天全部算進來
            span = self.i + 1
        else:
            # 棧頂是左邊第一個比今天貴的那天
            # 它和今天之間夾著的日子，價格全都不超過今天
            span = self.i - self.stack[-1][1]

        self.stack.append((price, self.i))
        return span
```

同一組輸入的棧變化：

```text
next(100) → 1    [(100,0)]
next( 80) → 1    [(100,0), (80,1)]
next( 60) → 1    [(100,0), (80,1), (60,2)]
next( 70) → 2    [(100,0), (80,1), (70,3)]           i=3, 棧頂 80 在 1 → 3-1 = 2
next( 60) → 1    [(100,0), (80,1), (70,3), (60,4)]
next( 75) → 4    [(100,0), (80,1), (75,5)]           i=5, 棧頂 80 在 1 → 5-1 = 4
next( 85) → 6    [(100,0), (85,6)]                   i=6, 棧頂 100 在 0 → 6-0 = 6
```

**注意這裡的 pop 一樣什麼都不用做。** 天數不是被累加保存的，而是**留在沒被彈掉的那個人身上** —— 棧頂的索引本來就標記了「上一個比今天貴的位置」，中間被吞掉幾天，相減自然就算出來了。

**要選哪一種？**

| | 累加天數 | 記錄索引 |
|---|---|---|
| 額外要維護的 | 無 | 一個計數器 `i` |
| 天數怎麼來 | 主動累加，資訊在被彈的人身上 | 被動相減，資訊在留下的人身上 |
| 跟 [739](/interview/coding/739-daily-temperatures) 的相似度 | 較低 | 高，兩題可以共用同一套直覺 |

累加版比較精簡；索引版的好處是它跟整個單調棧家族的寫法一致，不用為這題記一個特例。

## 補充

**跟 739 的對照**：

| | [739](/interview/coding/739-daily-temperatures) | 901 |
|---|---|---|
| 方向 | 往右找第一個更高 | 往左數連續不更高 |
| 資料 | 一次給完整個陣列 | **online，一次一個** |
| 棧裡存 | 索引（要算距離） | `[價格, 天數]` 或 `(價格, 索引)` |
| 等號 | 嚴格 `>` 才結算 | `<=` 就吞掉 |

**同一個模板的其他形狀** → [單調棧模板](/interview/coding/monotonic-stack-template)：[496. Next Greater Element I](/interview/coding/496-next-greater-element-i)、[84. Largest Rectangle in Histogram](/interview/coding/84-largest-rectangle-in-histogram)、[42. Trapping Rain Water](/interview/coding/42-trapping-rain-water)。

## 複雜度

- 時間 —— 單次 `next` 最壞是 $O(n)$（一路吞光整個棧），但**均攤是 $O(1)$**：每個價格一輩子只會被 push 一次、pop 一次，所以 $n$ 次呼叫的總成本是 $O(n)$
- 空間 $O(n)$ — 價格一路下跌時（例如 `[50, 40, 30]`），沒有人被吞掉，棧會留下每一天

其中 $n$ 是 `next` 被呼叫的次數。

這題是均攤分析的好例子：**看單次呼叫會覺得它是 $O(n)$，但那個 $O(n)$ 的代價是「之前 push 過 n 次」換來的，不可能連續發生。**