題目描述:給定整數陣列 temperatures,對每天回傳需要等待幾天才能遇到更高溫度;若之後不會有更高溫度則回傳 0。
解題思路:使用單調遞減堆疊(Monotonic Decreasing Stack)。堆疊中存放尚未找到「下一個更高溫」的日期索引。從左到右遍歷每天的溫度,若當天溫度高於堆疊頂端所代表的溫度,表示找到了答案:彈出堆疊頂端索引,計算天數差(當前索引 - 彈出索引)並記錄。持續彈出直到堆疊為空或頂端溫度不低於當前溫度,再將當前索引推入堆疊。最終堆疊中剩餘的索引答案為 0(已在初始化時設定)。
時間複雜度:O(n) — 每個索引最多被推入和彈出堆疊各一次,總操作次數為 O(2n) = O(n)。
空間複雜度:O(n) — 堆疊最壞情況(嚴格遞減溫度序列)儲存所有 n 個索引。
1. Initialize answer array of size n with all 0s
2. Initialize empty stack (stores indices)
3. For i from 0 to n-1:
a. While stack is not empty AND temperatures[i] > temperatures[stack.top()]:
- Pop index idx from stack
- answer[idx] = i - idx
b. Push i onto stack
4. Return answer (remaining stack indices already have answer = 0)暴力法 O(n²):對每天向右掃描找第一個更高溫度的日期。簡單但在最壞情況(嚴格遞減)下效率差。
從右到左 DP O(n):從右向左遍歷,利用已計算的跳躍結果快速向前跳過。answer[i] 由 answer[i+1] 推導,複雜度平均接近 O(n) 但最壞仍 O(n²),不如單調堆疊穩定。