---
title: "739. Daily Temperatures"
url: "https://laigary.com/interview/coding/739-daily-temperatures"
type: "note"
section: "coding"
date: "2025-04-02"
updated: "2026-07-27"
tags: ["Stack", "Monotonic", "Array"]
---

# 739. Daily Temperatures

[739. Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)

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

這是一個單調棧 [Monotonic](/interview/coding?tag=Monotonic) 的問題。我在兩次不同時間用了兩個不同的方向來想它，兩種都寫在下面。

## 思路

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

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

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

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

### 兩個方向的差別

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


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


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

## 解題方向

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

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

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

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

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

```python
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` 右邊第一個更高的日子，距離直接相減；棧空就代表後面沒有更暖的了

```python
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]`）：

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

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

## 補充

**幾乎是鏡像的題**：[901. Online Stock Span](/interview/coding/901-online-stock-span) 問的是「往**左**連續有幾天不比今天高」，方向相反但棧的邏輯一模一樣。

**同一個模板的其他形狀**：[496. Next Greater Element I](/interview/coding/496-next-greater-element-i)（下一個更大）、[84. Largest Rectangle in Histogram](/interview/coding/84-largest-rectangle-in-histogram)（往左右各能延伸多遠）、[42. Trapping Rain Water](/interview/coding/42-trapping-rain-water)（彈出的是凹槽底）。整套見 [單調棧模板](/interview/coding/monotonic-stack-template)。

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

## 複雜度

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

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