Intuition#

核心思路：用遞減單調堆疊，存 (價格, 跨度) 配對，遇到新價格時吸收所有小於等於它的棧頂跨度。

• 「往回找第一個比自己大的元素」是單調堆疊的經典應用
• 每次呼叫 next 時，把所有 <= 當前價格的棧頂 pop 掉，累計它們的跨度

Approaches#

⭐1: 單調遞減堆疊#

• 概念: 堆疊維護嚴格遞減的價格序列，每個元素記錄 (價格, 跨度)。新價格進來時，把所有 <= 它的元素彈出，累加跨度
• 時間複雜度: 每次 next 均攤 O(1)，總計 O(n)
• 空間複雜度: 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: 「往回找第一個更大/更小元素」或「連續滿足條件的區間長度」 = 單調堆疊
• 關鍵技巧: 堆疊中存 (值, 跨度) 配對，pop 時累加跨度，實現了跨度的「壓縮」，不需要存每一天的資料