901. Online Stock Span
每次餵進一個當日股價，回答「從今天往回數，連續有幾天的股價小於等於今天」。今天自己也算一天。
這個題目真的算是非常難，沒有寫過的話面試真的很難有機會寫出來。
思路
它是 739. Daily Temperatures 的鏡像 —— 739 往右找第一個更高的，這題往左數連續有幾天不比今天高。但有一個關鍵差異：
這題是 online 的。 資料一次來一個，看不到未來，而且答案必須當場回傳。739 可以選正向或反向掃，這題直接沒得選：只能由左往右，而且只能靠「過去」的資訊。
暴力解與它浪費在哪
最直覺的做法是把所有價格存成一個陣列，每次呼叫往回掃到第一個更高的價格 —— 單次 ， 次呼叫就是 。
浪費在哪？看這條丟棄規則：
如果今天的價格
>=昨天的，那昨天從此不必再單獨存在 —— 未來任何一天只要跨得過今天，就一定也跨得過昨天。
所以昨天可以被今天吸收掉。但不能直接丟掉，因為昨天代表的天數還算數 —— 它會被算進未來某一天的 span 裡。
最難的一步：想到要記錄天數
我卡最久的地方不是「該用單調棧」，而是想到棧裡要多存一個天數。
看到「往回數連續幾天」很自然就只想去存價格，然後就卡住了 —— 因為 pop 掉之後那幾天就消失了。但被吞掉的日子雖然不必再單獨比較，它們還要被算進未來某一天的 span 裡。
真正的關鍵認知是這一句：
pop 掉的東西不能就這樣消失，它帶著資訊。
想通之後，剩下的只是選一個載體來保存那個資訊 —— 把天數累加起來，或是記住位置之後再相減。兩種寫法下面都有。
棧裡存的不是價格，是「壓平的區間」
把被吞掉的天數併進今天，這就是解法的全部：
count = 1 # 今天自己
while 棧頂價格 <= 今天:
count += 棧頂的天數 # 把它的天數接收過來
pop
push([今天的價格, count])
棧裡的每一項代表一段已經被壓平的區間：price 是那一段的最高價（也就是那段最後一天的價格），count 是那一段涵蓋幾天。由底到頂，價格嚴格遞減。
739 存索引是為了算距離；這題把天數累加起來，連索引都不用維護。
等號的方向跟 739 相反
739 要的是嚴格更高才算答案；這題的 span 定義包含「小於或等於」，所以相等的價格要被吞掉。
while self.prices and self.prices[-1][0] <= price: # 901：<= 要吞
while stack and temperatures[i] > temperatures[stack[-1]]: # 739：> 才結算
兩題放在一起看的時候，等號特別容易記反。可靠的做法是每次都回到題目定義去推，而不是背 code。
解題方向
寫法一：累加天數
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] 跑一次，棧的變化把整個想法說得很清楚：
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。
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
同一組輸入的棧變化：
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 的相似度 | 較低 | 高，兩題可以共用同一套直覺 |
累加版比較精簡；索引版的好處是它跟整個單調棧家族的寫法一致，不用為這題記一個特例。
補充
跟 739 的對照：
| 739 | 901 | |
|---|---|---|
| 方向 | 往右找第一個更高 | 往左數連續不更高 |
| 資料 | 一次給完整個陣列 | online，一次一個 |
| 棧裡存 | 索引（要算距離） | [價格, 天數] 或 (價格, 索引) |
| 等號 | 嚴格 > 才結算 | <= 就吞掉 |
同一個模板的其他形狀 → 單調棧模板：496. Next Greater Element I、84. Largest Rectangle in Histogram、42. Trapping Rain Water。
複雜度
- 時間 —— 單次
next最壞是 （一路吞光整個棧），但均攤是 ：每個價格一輩子只會被 push 一次、pop 一次，所以 次呼叫的總成本是 - 空間 — 價格一路下跌時（例如
[50, 40, 30]），沒有人被吞掉，棧會留下每一天
其中 是 next 被呼叫的次數。
這題是均攤分析的好例子：看單次呼叫會覺得它是 ，但那個 的代價是「之前 push 過 n 次」換來的，不可能連續發生。