📘 題目敘述
給你一個整數陣列 temperatures，表示每天的氣溫。
請回傳一個陣列 answer，其中 answer[i] 表示：在第 i 天之後，還要等幾天才會遇到更高的溫度。
如果之後都不會再有更高溫，則 answer[i] == 0。
條件限制
1 <= temperatures.length <= 10^530 <= temperatures[i] <= 100
🧠 解題思路
這題如果直接做，會是：
- 對每一天
i - 往右找第一個比
temperatures[i]更高的溫度
但這樣很多位置會一直重複往右掃。
我這份做法是用 stack 來記：
前面那些還沒找到「下一個更高溫」的日期 index。
當我現在走到第 i 天，溫度是 temperatures[i] 時，
我就拿今天的溫度去看 stack 頂端那些還沒解決的日期。
如果：
temperatures[s.top()] < temperatures[i]
代表今天比 stack 頂端那天還熱，
那今天就是它要找的第一個更高溫日。
所以那一天的答案就可以直接算成：
i - s.top()
然後把那個 index 從 stack 裡 pop 掉。
如果 stack 頂端那天的溫度大於等於今天，表示：
- 今天還不夠熱
- 不能當它的答案
那就先停下來，最後再把今天這個 index push 進 stack，表示：
- 今天也還沒找到以後更高溫的那一天
- 要等未來的日子來幫它解決
最後如果 stack 裡還有剩下的 index，代表那些天之後都沒有更高溫，
而這份程式一開始就把 ans 設成 0，所以它們自然就維持 0。
也就是說，這題的核心就是：
用 stack 存前面還沒找到更高溫的日期，當新溫度出現時，就幫那些比它低的日期直接結算答案。
所有變數
s：stack，存還沒找到下一個更高溫的日期 indexn：陣列長度ans：答案陣列，ans[i]表示第i天還要等幾天才會遇到更高溫
🪜 主要流程步驟
1. 先準備 stack 和答案陣列
stack<int> s;
int n = temperatures.size();
vector<int> ans(n, 0);
這裡：
s用來放那些還沒找到更高溫日期的 indexans一開始全部設成0
這樣最後如果某些日期一直沒找到更高溫，就不用再另外補，直接保留 0 即可。
2. 依序掃過每一天的溫度
for (int i = 0; i < n; i++) {
這裡的 i 就是目前正在看的日期。
現在的目標是：
- 用今天的溫度
- 去幫前面那些還沒找到答案的日期做結算
3. 只要今天比 stack 頂端那天更熱，就幫那天算答案
如果今天的溫度 temperatures[i] 比 stack 頂端那天高，代表：
- 今天就是那一天之後第一個更高溫的日子
所以直接把答案設成：
i - s.top()
意思就是從那一天等到今天，總共隔了幾天。
然後把那個已經找到答案的 index pop 掉。
如果 stack 頂端那天的溫度大於等於今天，表示今天不夠熱，
那它的答案還不能決定，所以先停下來。
4. 為什麼今天一定是它「第一個」更高溫的日子
因為我們是從左到右掃。
某一天一旦第一次遇到右邊有更高的溫度，
那一天就是題目要的最小 index。
而 stack 裡放的都是：
- 前面還沒找到答案的日期
所以當某個日期第一次被今天這個溫度結算時，
今天自然就是它右邊第一個更高溫的日子。
5. 把今天這個日期 push 進 stack，等未來更熱的天來處理它
s.push(i);
當前面能被今天解決的日期都處理完之後，
就把今天的 index i 放進 stack。
代表：
- 今天目前還沒找到未來更高溫的日子
- 之後要靠右邊新的溫度來幫它結算
6. 為什麼最後不用特別處理 stack 裡剩下的日期
因為你的 ans 是這樣初始化的：
vector<int> ans(n, 0);
所以如果某些日期一路到最後都沒有被 pop 出來，
代表它們之後沒有更高溫。
而題目要求這種情況答案就是 0，所以直接保持原本的值就可以，不需要再額外補。
7. 最後回傳答案
return ans;
當整個陣列都掃完後，ans 就是每一天要等多久才會遇到更高溫的結果。
⏱️ 複雜度
設 n = temperatures.length。
- 時間複雜度：
O(n)
每個 index 最多只會被 push 進 stack 一次、pop 出來一次。 - 空間複雜度：
O(n)
stack 最壞情況下可能存下所有日期 index，答案陣列也需要O(n)空間。
💻 程式碼實作
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> s;
int n = temperatures.size();
vector<int> ans(n, 0);
for (int i = 0; i < n; i++) {
while (!s.empty()) {
if (temperatures[s.top()] < temperatures[i]) {
ans[s.top()] = i - s.top();
s.pop();
} else {
break;
}
}
s.push(i);
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/daily-temperatures/