LeetCode 解題筆記：739. Daily Temperatures

作者：王一哲
日期：2026年9月22日


LeetCode 題目連結：739. Daily Temperatures

解題想法

中等難度題，題目一個表示每日氣溫的整數陣列 $temperatures$，要找出每一天要在幾天之後才會遇到更高的氣溫，如果之後沒有任何一天的氣溫更高，則當天的答案為 0。這題很適合用堆疊處理，開一個堆疊 $st$，用來記錄目前已經讀到、而且還沒有找到答案的氣溫及索引值。用一個 for 迴圈讀取每天的氣溫 $t$ 及索引值 $i$；再用一個 while 迴圈，如果 $st$ 之中有資料而且 $t$ 大於 $st$ 最後一項的氣溫，移除 $st$ 的最後一項，如果這項的索引值為 $pre$，則這項對應的答案為 $pre - i$；跑完 while 迴圈之後再加入 $(t, i)$。

Python 程式碼

Runtime: 97 ms, beats 50.76%. Memory: 34.32 MB, beats 21.54%.

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        ans = [0] * len(temperatures)  # 答案
        st = []  # 堆疊，放入 (t, idx)
        
        for i, t in enumerate(temperatures):
            # 如果 st 有資料，t 大於 st 最後一項的溫度
            while st and t > st[-1][0]:
                pre = st.pop()[1]  # 移除 st 最後一項
                ans[pre] = i - pre  # 這項的索引值答案為 i - pre
            # (t, i) 加入 st
            st.append((t, i))
        return ans

C++ 程式碼

Runtime: 33 ms, beats 14.56%. Memory: 111.67 MB, beats 8.70%.

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = (int)temperatures.size();
        vector<int> ans (n, 0);
        stack<pair<int, int>> st;
        for(int i = 0; i < n; i++) {
            int t = temperatures[i];
            while(!st.empty() && t > st.top().first) {
                int pre = st.top().second;
                st.pop();
                ans[pre] = i - pre;
            }
            st.push(make_pair(t, i));
        }
        return ans;
    }
};

Runtime: 32 ms, beats 16.97%. Memory: 111.81 MB, beats 6.17%.

class Solution {
private:
    struct Data {
        int t, idx;
    };
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = (int)temperatures.size();  
        vector<int> ans (n, 0);  // 答案
        stack<Data> st;  // 堆疊，放入 (t, idx)
        
        for(int i = 0; i < n; i++) {
            int t = temperatures[i];
            // 如果 st 有資料，t 大於 st 最後一項的溫度
            while(!st.empty() && t > st.top().t) {
                int pre = st.top().idx;
                st.pop();  // 移除 st 最後一項
                ans[pre] = i - pre;  // 這項的索引值答案為 i - pre
            }
            // (t, i) 加入 st
            st.push({t, i});
        }
        return ans;
    }
};