Daily Temperatures

題目描述

給定每日溫度陣列 temperatures，回傳一個陣列 answer，其中 answer[i] 是從第 i 天開始要等幾天才有更高溫度。如果之後都沒有更高溫度，則為 0。

輸入：temperatures = [73,74,75,71,69,72,76,73]
輸出：[1,1,4,2,1,1,0,0]

解題思路

初始化

建立空的 Stack（存索引而非溫度值），建立 answer 陣列初始化為全 0

遍歷每一天

for i = 0 到 n-1，取出 temperatures[i] 作為當前溫度

彈出較冷的

while Stack 非空且 temperatures[i] > temperatures[stack.peek()]：彈出 prevIdx，設 answer[prevIdx] = i - prevIdx

壓入當前索引

將 i 壓入 Stack，等待未來某天的更高溫度來彈出它

Stack 剩餘

遍歷結束後 Stack 中剩餘的索引表示之後沒有更高溫度，answer 維持初始值 0

程式碼

C#

csharp

public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        int n = temperatures.Length;
        int[] answer = new int[n];
        var stack = new Stack<int>(); // 存索引
        
        for (int i = 0; i < n; i++) {
            // 當前溫度比 stack 頂端更高 → 找到更暖的天
            while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()]) {
                int prevIdx = stack.Pop();
                answer[prevIdx] = i - prevIdx;
            }
            stack.Push(i);
        }
        return answer; // Stack 中剩餘的索引，answer 自動是 0
    }
}

TypeScript

typescript

function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;
    const answer = new Array(n).fill(0);
    const stack: number[] = []; // 存索引
    
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const prevIdx = stack.pop()!;
            answer[prevIdx] = i - prevIdx;
        }
        stack.push(i);
    }
    return answer;
}

Python

python

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # 存索引
    
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            answer[prev_idx] = i - prev_idx
        stack.append(i)
    
    return answer

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(n) |

雖然有 while 迴圈嵌套在 for 迴圈內，但每個索引最多被 push 和 pop 各一次，總操作數 ≤ 2n，因此時間 O(n)。Stack 最大深度為 n（溫度單調遞減時），空間 O(n)。

邊界情況

溫度單調遞減：例如 [5,4,3,2,1]，沒有任何天之後有更高溫度，answer 全為 0。Stack 不斷累積、不彈出
溫度單調遞增：例如 [1,2,3,4,5]，每個新溫度都比前一個高，answer = [1,1,1,1,0]。每個元素 push 後立刻被下一個彈出
所有溫度相同：例如 [30,30,30]，相同溫度不算更高，answer 全為 0

圖解

Day 0: 73°

74>73 彈出→

Day 1: 74°

→

Stack (遞減): [75, 71, 69]

新溫度→

Day 5: 72° 來了

比較→

彈出 69, 71 (比72冷)

計算天數差→

answer[4]=1, answer[3]=2

圖表展示 Stack 的彈出機制：當 Day 5 的 72° 到來時，Stack 頂端的 69°（Day 4）和 71°（Day 3）都比 72° 冷，依序被彈出。彈出時計算天數差：answer[4] = 5-4 = 1，answer[3] = 5-3 = 2。

進階觀點

💡面試追問

Q: 為什麼是 O(n) 而不是 O(n^2)？ A: 雖然有 while 迴圈，但每個索引最多被 push 一次和 pop 一次，所以 push 總次數 ≤ n，pop 總次數 ≤ n，整體操作數 ≤ 2n = O(n)。這是「均攤分析」的經典案例。
Q: Stack 為什麼存索引而不是溫度值？ A: 因為需要用索引計算天數差 answer[prevIdx] = i - prevIdx。如果只存溫度值，就無法知道那一天是哪一天。溫度值可以透過 temperatures[stack.peek()] 間接取得。
Q: 這個模式還能用在哪些題？ A: 這是「單調遞減 Stack」的經典應用。LeetCode 496/503（Next Greater Element I/II）、42（Trapping Rain Water）、84（Largest Rectangle in Histogram）都用同樣的「遇到更大元素就彈出」模式。
Q: 如果要找「之前最近的更暖天」？ A: 從右往左遍歷，用同樣的單調 Stack。或者在結果陣列上反推：如果 answer[j] 指向 i，代表 i 是 j 之後最近的更暖天，反過來 j 就是 i 之前最近的更暖天。

理解測驗

🤔 為什麼 Stack 中的溫度保持遞減（從底到頂）？

🤔 遍歷結束後 Stack 中還有元素，它們的 answer 值是什麼？