739. Daily Temperatures

──────────────────────────────────────────────────────────────────────

給一串每日氣溫，對每一天回答「還要等幾天才會遇到更高的溫度」，等不到就填 0。

這是一個單調棧 Monotonic 的問題。我在兩次不同時間用了兩個不同的方向來想它，兩種都寫在下面。

思路

暴力解很直覺：對每一天往右掃到第一個更高的溫度， $O (n^{2})$ 。

要降到 $O (n)$ ，得先看出哪些比較是白做的。關鍵是一個丟棄規則：

如果 j 在 i 右邊而且 t[j] >= t[i]，那 i 從此再也不可能是任何人的答案 —— 因為更右邊的日子如果要找「左邊第一個更高的」，一定會先撞到更近的 j。

有東西可以永久丟掉，就代表可以用一個棧把還「活著」的候選維護起來，而每個索引只會進棧一次、出棧一次。這就是單調棧的全部。

兩個方向的差別

同一題可以從兩個方向掃，差別不在寫法，而在棧裡裝的是什麼：

	正向（過去 → 未來）	反向（未來 → 過去）
棧裡裝的是	還沒找到答案的日子	未來的候選答案
當前的 `i` 扮演	解答者 —— 一次結算掉好幾個人	提問者 —— 自己查棧頂
答案何時寫下	被 `pop` 的那一刻	`push` 之前
棧由底到頂	非遞增	嚴格遞減

想通這件事之後，兩份程式碼就不是兩個要背的東西，而是同一個結構的兩面。

解題方向

正向：棧裡存「還在等答案的人」

其實這應該是比較直覺的想法，但我第一次做的時候反而沒有想到，因為我卡在：遍歷到當下時，需要更新答案的 index 相對於當前 index 都在「過去」，我不知道怎麼記錄過去的 index 來幫我。第二次才想到 —— 就讓棧去記錄過去。

站在當前的 i，要做兩件判斷：

棧是否為空？不為空代表過去有記錄的日子還沒遇到更暖的
當前氣溫是否比棧頂那天高？是的話就可以更新答案 —— 因為「現在」正是那一天遇到的第一個更暖的日子

兩個條件同時成立時，就把過去的座標 pop 出來，答案剛好是兩個座標的差距。

class Solution:
    def dailyTemperatures(self, 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]]:
                idx = stack.pop()
                answer[idx] = i - idx
            stack.append(i)
        
        return answer

while 而不是 if —— 一個溫暖的日子可能一次解救掉好幾天。而因為棧是非遞增的，那些人一定連續地疊在棧頂，不會漏也不會多。

跑完之後還留在棧裡的人怎麼辦？ 他們就是「後面沒有更暖的日子」的那些，答案是 0 —— 而 answer = [0] * n 的初始化已經免費處理掉了，不需要在迴圈外再寫一段清空邏輯。

反向：棧裡存「候選答案」

老實說我忘了我一開始為何選擇這樣做了，但我有當時的筆記。

從後往前掃的時候，棧裡維護的是「i 右邊那些還可能當答案的日子」。走到 i 時：

先把棧裡溫度 <= t[i] 的全部丟掉。它們對 i 和 i 更左邊的所有日子都沒用了 —— 因為 i 自己更近、而且不比它們低。這是最上面那條丟棄規則的直接應用
丟完之後，棧頂如果還有東西，那就是 i 右邊第一個更高的日子，距離直接相減；棧空就代表後面沒有更暖的了

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        n = len(temperatures) 
        res = [0] * n
        s = []

        for i in reversed(range(n)):
            while s and temperatures[s[-1]] <= temperatures[i]:
                s.pop()
            res[i] = 0 if not s else s[-1] - i
            s.append(i)
        
        return res

這個版本 pop 出來的東西什麼都不用做，因為被丟掉的是「已經沒用的候選」而不是「還在等答案的人」。這是跟正向版最大的體感差異。

兩個比較運算子是互補的

這是這題最容易寫錯的一行，而且錯了不會爆炸，只在溫度相等的時候悄悄給錯答案：

	正確	寫錯成
正向	`temperatures[i] > temperatures[stack[-1]]`	`>=`
反向	`temperatures[s[-1]] <= temperatures[i]`	`<`

拿 [30, 30, 31] 驗一次（正解 [2, 1, 0]）：

正向 >   → [2, 1, 0]   ✅
正向 >=  → [1, 1, 0]   ❌  第 0 天被第 1 天「解救」了，但它們一樣暖
反向 <=  → [2, 1, 0]   ✅
反向 <   → [1, 1, 0]   ❌  同一個錯，換個方向犯

題目要的是嚴格更高，所以正向必須用嚴格的 > 才結算，反向必須把 <= 的全丟掉。兩邊的等號位置剛好相反，這也是為什麼分開記兩份很容易搞混 —— 記住題意是「嚴格」，再推導等號該放哪邊比較穩。

補充

幾乎是鏡像的題：901. Online Stock Span 問的是「往左連續有幾天不比今天高」，方向相反但棧的邏輯一模一樣。

同一個模板的其他形狀：496. Next Greater Element I（下一個更大）、84. Largest Rectangle in Histogram（往左右各能延伸多遠）、42. Trapping Rain Water（彈出的是凹槽底）。整套見單調棧模板。

別跟 239. Sliding Window Maximum 搞混：那題也維護單調結構，但用的是雙端佇列，因為左邊會因為視窗滑出而過期 —— 單調棧只從一端進出，沒有過期這件事。

複雜度

時間 $O (n)$ — 雖然有巢狀迴圈，但每個索引最多進棧一次、出棧一次，while 的總執行次數受限於 push 的總次數，是均攤 $O (n)$
空間 $O (n)$ — 溫度一路下降時（例如 [50, 40, 30]），所有索引都會留在棧裡

其中 $n$ 是天數。輸出陣列不計入額外空間。