Online Stock Span
題目描述
設計一個類別 StockSpanner，每次呼叫 next(price) 回傳包含今天在內的連續天數中，股價都 ≤ 今天的天數。
StockSpanner sp = new StockSpanner();
sp.next(100); // 1
sp.next(80); // 1
sp.next(60); // 1
sp.next(70); // 2 (60, 70)
sp.next(60); // 1
sp.next(75); // 4 (60, 70, 60, 75... 等等回到 80 停)
sp.next(85); // 6
解題思路
Stack 存配對
Stack 中每個元素是 (price, span) 配對，維護從底到頂嚴格遞減的價格序列
新價格進來
初始 span = 1（至少包含今天自己），例如價格 75 進來，span 從 1 開始
合併較小的
Stack 頂端的 price ≤ 當前 price → 彈出並累加其 span。例如彈出 (60,1) 後 span 變成 2，再彈出 (70,2) 後 span 變成 4
壓入 Stack
將 (price, 累積的 span) 壓入 Stack，例如壓入 (75, 4)
回傳 span
回傳當前的 span 值作為答案
程式碼
C#
public class StockSpanner {
private Stack<(int price, int span)> stack;
public StockSpanner() {
stack = new Stack<(int, int)>();
}
public int Next(int price) {
int span = 1;
// 合併所有 <= 當前價格的記錄
while (stack.Count > 0 && stack.Peek().price <= price) {
span += stack.Pop().span;
}
stack.Push((price, span));
return span;
}
}TypeScript
class StockSpanner {
private stack: [number, number][]; // [price, span]
constructor() {
this.stack = [];
}
next(price: number): number {
let span = 1;
while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
span += this.stack.pop()![1];
}
this.stack.push([price, span]);
return span;
}
}Python
class StockSpanner:
def __init__(self):
self.stack = [] # [(price, span)]
def next(self, price: int) -> int:
span = 1
# 合併所有 <= 當前價格的歷史記錄
while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1]
self.stack.append((price, span))
return span複雜度分析
| | Time | Space | |--|------|-------| | 每次 next() | 均攤 O(1) | O(n) |
- Time：每個元素最多被 push 一次和 pop 一次，n 次
next()呼叫的總操作數 ≤ 2n，平均每次 O(1) - Space：最壞情況下（嚴格遞減序列）Stack 保存所有 n 個元素，所以是 O(n)
邊界情況
- 第一次呼叫：Stack 為空，不進入 while 迴圈，span = 1 直接回傳
- 嚴格遞減序列（如 100, 90, 80, 70）：每次都不觸發合併，Stack 持續增長，每次 span = 1
- 嚴格遞增序列（如 10, 20, 30, 40）：每次都把 Stack 清空合併，span 依序為 1, 2, 3, 4
- 所有價格相同（如 50, 50, 50）：每次合併前一個，span 依序為 1, 2, 3（因為
<=包含等於）
圖解
圖表展示了價格 75 進來時的合併過程：先彈出 (60,1) 再彈出 (70,2)，累計 span=1+1+2=4。 遇到 (80,1) 時 80 > 75 停止合併，最終壓入 (75,4)。被彈出的記錄已被 75 的 span 吸收。
進階觀點
💡面試追問
Q: 為什麼是均攤 O(1)？
A: 每個元素最多被 push 一次和 pop 一次。n 次 next() 的總操作數 ≤ 2n（n 次 push + 最多 n 次 pop），均攤每次操作 O(2n/n) = O(1)。雖然單次 next() 最壞可能 pop 掉所有元素（O(n)），但那些元素之後不會再被 pop，總量固定。
Q: Stack 中存 span 而不是逐一記錄每天的好處？ A: 合併後的 span 保留了「被吞掉的天數」資訊。如果只存 price，被彈出後就無法知道它代表了幾天，必須逐天回溯，單次操作就不是 O(1) 了。
Q: 和 739. Daily Temperatures 的對比？ A: Daily Temperatures 找「下一個更大的」（Next Greater Element），本題找「前面連續不大於的跨度」（Previous Greater Element）。兩者都用單調遞減 Stack，是同一概念的正反方向應用。
Q: 如果要支援「撤銷上一次操作」怎麼做？
A: 需要額外記錄每次 next() 被彈出的元素列表。撤銷時把它們重新 push 回 Stack，並移除最後壓入的元素。相當於一個 undo stack 疊加在原有結構上。
理解測驗
🤔 為什麼 Stack 中要存 (price, span) 而不只是 price？
🤔 如果連續輸入遞減的價格 [100, 90, 80, 70]，Stack 的狀態是什麼？