題目
#

leetcode 739 - Daily Temperatures (題目說明請點連結)

題目簡述
#

給定一個整數陣列 temperatures，表示每天的温度，返回一個陣列 answer，其中 answer[i] 是指在第 i 天之後，要等多少天才會出現更高的温度。

範例
#

Example 1:

Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation: 在第 0 天後的 1 天內會變暖（74 比 73 高）。

Example 2:

Input: temperatures = [30, 40, 50, 60]
Output: [1, 1, 1, 0]
Explanation: 每天後都會變暖，除了最後一天。

Example 3:

Input: temperatures = [30, 60, 90]
Output: [1, 1, 0]
Explanation: 每天後都會變暖，除了最後一天。

解題思路
#

這題要求找到每一天之後幾天會出現更高的溫度。

解法：單調遞減堆疊（Monotonic Stack）

建立一個 Stack 來存儲溫度的索引。
從後往前遍歷 temperatures 陣列。
如果當前溫度 temperatures[i] 大於等於堆疊頂端對應的溫度，則彈出堆疊。
如果堆疊非空，則計算與堆疊頂端的索引相差的天數，存入結果陣列。
將當前索引推入堆疊。

這種方法確保堆疊內的索引對應的溫度是遞減的，從而能夠快速找到下一個更高的溫度。

以 Example 1 為例：

輸入：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
初始化結果陣列 res = [0,0,0,0,0,0,0,0]，堆疊 stack = []

從後往前遍歷：

i = 7，溫度 73，堆疊為空，res[7]=0，stack=[7]
i = 6，溫度 76，stack.top=7 (73 < 76)，所以 stack 清空，res[6]=0，stack=[6]
i = 5，溫度 72，stack.top=6 (76 > 72)，res[5]=6-5=1，stack=[6,5]
i = 4，溫度 69，stack.top=5 (72 > 69)，res[4]=5-4=1，stack=[6,5,4]
i = 3，溫度 71，stack.top=4 (69 < 71)，彈出4，stack.top=5 (72 > 71)，res[3]=5-3=2，stack=[6,5,3]
i = 2，溫度 75，stack.top=3 (71 < 75)，彈出3，stack.top=5 (72 < 75)，彈出5，stack.top=6 (76 > 75)，res[2]=6-2=4，stack=[6,2]
i = 1，溫度 74，stack.top=2 (75 > 74)，res[1]=2-1=1，stack=[6,2,1]
i = 0，溫度 73，stack.top=1 (74 > 73)，res[0]=1-0=1，stack=[6,2,1,0]

最終結果 res = [1, 1, 4, 2, 1, 1, 0, 0]

這代表：

第 0 天後 1 天會變暖（74 > 73）
第 1 天後 1 天會變暖（75 > 74）
第 2 天後 4 天會變暖（76 > 75）
以此類推

完整程式碼
#

java

import java.util.Stack;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n]; // 用來存放每一天要等幾天才會變暖
        Stack<Integer> stack = new Stack<>(); // 單調遞減堆疊，存放溫度的索引

        // 從後往前遍歷溫度陣列
        for (int i = n - 1; i >= 0; i--) {
            // 如果堆疊不為空，且當前溫度大於等於堆疊頂端的溫度，則彈出堆疊
            while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
                stack.pop();
            }
            // 如果堆疊不為空，代表堆疊頂端的索引對應的溫度比當前高
            if (!stack.isEmpty()) {
                res[i] = stack.peek() - i; // 計算距離
            }
            // 將當前索引壓入堆疊
            stack.push(i);
        }

        return res;
    }
}