給定每日溫度陣列
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
TIP
核心思路：用遞減單調堆疊，遇到更高溫度時，將所有比它低的棧頂元素彈出並計算天數差。
- 「找下一個更大的元素」是單調堆疊 (Monotonic Stack) 的經典場景
- 維護一個遞減堆疊（棧底到棧頂遞減），新元素比棧頂大時，棧頂找到了答案
- 堆疊中存索引而非值，方便計算天數差
Approaches
1. Brute Force — O(n^2) / O(1)
- Idea: 對每一天，往後掃描找到第一個更高溫度
- Time:
O(n^2)- 最壞情況遞減序列 - Space:
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)
- Idea: 遍歷陣列，維護遞減單調堆疊（存索引）。當前溫度高於棧頂時，棧頂的答案就是索引差，彈出並記錄
- Time:
O(n)- 每個元素最多入棧出棧各一次 - Space:
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
}
}WARNING
堆疊中存的是「索引」而非溫度值，這樣才能計算天數差。單調堆疊從棧底到棧頂是遞減的（對應的溫度值），保證每個元素在找到下一個更大元素時被正確處理。
🔑 Takeaways
- Pattern: 「下一個更大/更小元素」問題 = 單調堆疊 (Monotonic Stack)
- Key trick: 堆疊中存索引而非值；遞減堆疊找「下一個更大」，遞增堆疊找「下一個更小」；每個元素最多入棧出棧各一次，所以總體 O(n)