739. Daily Temperatures

Medium

Description

給定每日溫度陣列 temperatures，回傳一個陣列 answer，其中 answer[i] 代表在第 i 天之後，需要等幾天才會出現更高的溫度。若之後沒有更高溫度，則 answer[i] = 0。

Example:

Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]

Intuition#

核心思路：用遞減單調堆疊，遇到更高溫度時，將所有比它低的棧頂元素彈出並計算天數差。

「找下一個更大的元素」是單調堆疊 (Monotonic Stack) 的經典場景
維護一個遞減堆疊（棧底到棧頂遞減），新元素比棧頂大時，棧頂找到了答案
堆疊中存索引而非值，方便計算天數差

Approaches#

1: Brute Force#

概念: 對每一天，往後掃描找到第一個更高溫度
時間複雜度: O(n^2) - 最壞情況遞減序列
空間複雜度: O(1) - 不含輸出陣列

class Solution {
    fun dailyTemperatures(temperatures: IntArray): IntArray {
        val n = temperatures.size
        val answer = IntArray(n)

        for (i in 0 until n) {
            for (j in i + 1 until n) {
                if (temperatures[j] > temperatures[i]) {
                    answer[i] = j - i
                    break
                }
            }
        }

        return answer
    }
}

⭐2: Monotonic Stack#

概念: 遍歷陣列，維護遞減單調堆疊（存索引）。當前溫度高於棧頂時，棧頂的答案就是索引差，彈出並記錄
時間複雜度: O(n) - 每個元素最多入棧出棧各一次
空間複雜度: O(n) - 堆疊最多存 n 個索引

class Solution {
    fun dailyTemperatures(temperatures: IntArray): IntArray {
        val n = temperatures.size
        val answer = IntArray(n)
        val stack = ArrayDeque<Int>() // 存索引

        for (i in 0 until n) {
            while (stack.isNotEmpty() && temperatures[i] > temperatures[stack.last()]) {
                val prevIndex = stack.removeLast()
                answer[prevIndex] = i - prevIndex
            }
            stack.addLast(i)
        }

        return answer
    }
}

堆疊中存的是「索引」而非溫度值，這樣才能計算天數差。單調堆疊從棧底到棧頂是遞減的（對應的溫度值），保證每個元素在找到下一個更大元素時被正確處理。

🔑 Takeaways#

Pattern: 「下一個更大/更小元素」問題 = 單調堆疊 (Monotonic Stack)
關鍵技巧: 堆疊中存索引而非值；遞減堆疊找「下一個更大」，遞增堆疊找「下一個更小」；每個元素最多入棧出棧各一次，所以總體 O(n)