設計一個類別
StockSpanner，收集每日股票價格並回傳該日股票價格的跨度 (span)。跨度定義為從今天開始往回數，股價連續小於等於今天價格的天數（包含今天）。
Example:
Input: [“StockSpanner”, “next”, “next”, “next”, “next”, “next”, “next”, “next”], [[], [100], [80], [60], [70], [60], [75], [85]] Output: [null, 1, 1, 1, 2, 1, 4, 6]
Intuition
TIP
核心思路：用遞減單調堆疊，存 (價格, 跨度) 配對，遇到新價格時吸收所有小於等於它的棧頂跨度。
- 「往回找第一個比自己大的元素」是單調堆疊的經典應用
- 每次呼叫
next時，把所有 <= 當前價格的棧頂 pop 掉，累計它們的跨度
Approaches
1. Brute Force: Store Prices, Scan Back — O(n) per call / O(n)
- Idea: 把每天價格存進清單，每次
next從尾端往回數連續 ≤ 當前價的天數 - Time: 每次
next最差O(n)，總計O(n²) - Space:
O(n)- 儲存所有價格
class StockSpanner() {
private val prices = ArrayList<Int>()
fun next(price: Int): Int {
prices.add(price)
var span = 0
var i = prices.size - 1
while (i >= 0 && prices[i] <= price) { span++; i-- }
return span
}
}⭐ 2. Monotonic Decreasing Stack — amortized O(1) / O(n)
- Idea: 堆疊維護嚴格遞減的價格序列，每個元素記錄 (價格, 跨度)。新價格進來時，把所有 <= 它的元素彈出，累加跨度
- Time: 每次
next均攤O(1)，總計O(n) - Space:
O(n)
class StockSpanner() {
// Pair: (price, span)
private val stack = ArrayDeque<Pair<Int, Int>>()
fun next(price: Int): Int {
var span = 1
while (stack.isNotEmpty() && stack.last().first <= price) {
span += stack.removeLast().second
}
stack.addLast(price to span)
return span
}
}🔑 Takeaways
- Pattern: 「往回找第一個更大/更小元素」或「連續滿足條件的區間長度」 = 單調堆疊
- Key trick: 堆疊中存 (值, 跨度) 配對，pop 時累加跨度，實現了跨度的「壓縮」，不需要存每一天的資料