原文題目

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

題目摘要

1. 問題描述：給定一個整數陣列 temperatures，表示每天的氣溫。你的目標是回傳一個同樣大小的陣列 answer，使得 answer[i] 表示從第 i 天起，等待幾天能夠有更高的氣溫。如果沒有這樣的未來天數，則 answer[i] 應為 0。
2. 輸入：一個整數陣列 temperatures。
3. 輸出：回傳整數陣列 answer。

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

解題思路

1. 定義結果陣列與索引堆疊：
   • 創建一個與 temperatures 大小相同的 answer 陣列，初始值都設為 0。
   • 使用一個堆疊來幫助我們記錄未來的氣溫索引。
2. 遍歷氣溫：
   • 從最後一天開始，逐天向前遍歷 temperatures 陣列。
   • 對於每一天的氣溫，檢查堆疊中的氣溫索引。
3. 處理堆疊：
   • 如果堆疊不為空，並且當前氣溫高於堆疊頂端的氣溫，表示我們找到了比堆疊頂端氣溫更高的氣溫。
   • 可以根據堆疊頂端的索引計算等待的天數，並更新 answer 陣列。
   • 此後，將堆疊中的索引移除，因為這些天的氣溫已經不再是未來更高氣溫的候選。
4. 推入堆疊：
   • 每處理完一天後，將該天的索引加入堆疊，以便後續的天數能夠使用。
5. 回傳結果：
   • 遍歷結束後，answer 陣列將包含每一天等待更高氣溫的天數。

程式碼

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        //創建一個與temperatures大小相同的answer陣列
        int[] answer = new int[temperatures.length];
        //使用堆疊來儲存氣溫的索引
        Stack<Integer> tIndex = new Stack<>();
        //從最後一天開始遍歷temperatures陣列
        for (int i = temperatures.length - 1; i >= 0; i--) {
            //當堆疊不為空且當前氣溫大於或等於堆疊頂端氣溫時，移除堆疊頂端元素
            while (!tIndex.isEmpty() && temperatures[i] >= temperatures[tIndex.peek()]) {
                tIndex.pop();
            }
            //如果堆疊仍然有元素，則計算等待的天數
            if (!tIndex.isEmpty()) {
                answer[i] = tIndex.peek() - i; //answer[i]：堆疊頂端索引減去當前索引 i
            }
            tIndex.push(i); //將當前索引i加入堆疊，以供後續天數的比較
        }
        return answer; //回傳結果陣列
    }
}

結論： 這題有點像你每天早上出門前看天氣，想知道什麼時候會變暖一點，好決定要不要多穿一件外套。假設有一周的氣溫預測，你要算出每一天還要等幾天才能換上輕便的衣服。如果某天之後再也不會變暖，那當天就記作 0。我們用一個「待辦清單」來記錄那些還沒變暖的日子，從最後一天開始往前看。每當發現更暖的一天，就把那天標記下來，這樣可以快速計算出每一天要等多久，避免浪費時間逐天比較。