901. Online Stock Span

Online Stock Span

題目描述：設計 StockSpanner 類別，實作 next(price) 方法：每次呼叫代表今天的股票價格為 price，回傳今天及往前連續多少天的價格都 ≤ price（包含今天本身，即 span ≥ 1）。

解題思路：

此題是典型的線上資料流問題，每次 next() 呼叫必須在 O(1) 均攤時間內回答。

觀察：若某天的 span 為 s，表示它「吸收」了前面 s-1 天（這些天的價格都 ≤ 它）。因此，當新的一天到來時，若它比之前某天的價格更高，可以直接跳過那一天以及那一天已吸收的所有天。

使用單調遞減棧，棧中存 (price, span) 對：

1. 初始化 totalSpan = 1（今天本身算一天）。
2. 彈出所有棧頂 (p, s)，其中 p <= price：
   • 因為今天的價格 ≥ 那天，那天所代表的所有天都 ≤ 今天。
   • 累加：totalSpan += s。
3. 將 (price, totalSpan) 推入棧。
4. 回傳 totalSpan。

以呼叫序列 [100, 80, 60, 70, 60, 75, 85] 為例：

• next(100)：棧空，推入 (100,1)，span=1
• next(80)：80 < 100，推入 (80,1)，span=1
• next(60)：60 < 80，推入 (60,1)，span=1
• next(70)：70 ≥ 60 → 彈 (60,1) 累加，span=2；70 < 80 停止，推入 (70,2)
• next(60)：60 < 70，推入 (60,1)，span=1
• next(75)：75 ≥ 60 → 彈 (60,1) 累加 span=2；75 ≥ 70 → 彈 (70,2) 累加 span=4；75 < 80 停止，推入 (75,4)
• next(85)：85 ≥ 75 → 彈 (75,4) 累加 span=5；85 ≥ 80 → 彈 (80,1) 累加 span=6；85 < 100 停止，推入 (85,6)
• 回傳序列：[1, 1, 1, 2, 1, 4, 6]

時間複雜度：O(1) 均攤 — 每個價格點最多入棧和出棧各一次。對 n 次 next() 呼叫，棧操作總次數為 O(n)，每次呼叫的均攤時間為 O(1)。

空間複雜度：O(n) — 棧最多儲存 n 個 (price, span) 對（嚴格遞減序列時，每個元素都留在棧中）。

替代方法

方法一：線性掃描（暴力）

每次 next(price) 從歷史紀錄的最後一筆往前線性掃描，直到遇到比 price 大的那天為止，統計天數。

時間複雜度：O(n) 每次呼叫，O(n²) 總體｜空間複雜度：O(n)

邏輯直觀，但在資料流很長時效能退化明顯。

方法二：存陣列 + 二分搜尋（不適用）

歷史價格無排序規律，無法直接二分搜尋連續 span 的邊界。需要額外資料結構輔助，複雜度不優於單調棧。

方法三：單調棧存 (price, span)（推薦，本題解法）

span 的設計是此題的精髓：每個棧元素「代表」自己及其已吸收的歷史天數，使得跳過時可以一次性累加大片區間，實現 O(1) 均攤。

時間複雜度：O(1) 均攤｜空間複雜度：O(n)

延伸問題

1. Daily Temperatures（LeetCode 739）：同樣是「往後找更高溫度」的問題，但給定完整陣列而非線上資料流。思考兩題的棧設計差異：739 棧存索引（需計算距離），901 棧存 (price, span)（直接累加天數）。

2. 擴展為雙向 span：若 next(price) 需回傳前後各幾天 ≤ price（即今天為中心的最大連續區間），應如何修改？提示：需要同時維護一個「反向」的資料結構記錄未來資訊，會打破線上（online）特性。

3. Largest Rectangle in Histogram（LeetCode 84）：同樣需要計算每個柱子「向左延伸多少根不低於它的柱子」，概念與 span 累加類似。比較兩題如何利用單調棧一次性跳過多個已處理的區間，體會 span 壓縮技巧的通用性。