LeetCode #739 Daily Temperatures 每日溫度 – 解答與翻譯

英文原文如下

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 i^th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

中文翻譯

給予一個整數陣列 temperatures 代表每日的溫度，回傳一個陣列 answer，answer[i] 是你在第 i 天需要再等多少才會出現更溫暖的天氣。 如果未來沒有一天比當天熱，則讓 answer[i] 保持 0。

範例及題目限制

💡提示 1

If the temperature is say, 70 today, then in the future a warmer temperature must be either 71, 72, 73, …, 99, or 100. We could remember when all of them occur next.

要是今天的溫度是 70，那在未來一個比較熱的溫度可以是 71, 72, 73, …, 99, 或 100，我們可以記錄他們的下一次出現。

解題思路

相信有些人在看到這一題的時候(包括我)，想說那就用兩個 for 迴圈啊，就可以判斷了~

其實，這一題還有另一個解決辦法，那就是使用 堆疊 (Stack)，用到它的後進先出(LIFO)特性

C# 解決方案

方案1

public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        Stack<int> stack = new Stack<int>();
        int[]res = new int[temperatures.Length];

        for(var i=0; i<temperatures.Length; i++){
            while(stack.Count != 0 &&temperatures[i] > temperatures[stack.Peek()]){
                var top = stack.Pop();
                res[top] = i-top;
            }
            stack.Push(i);
        }
        return res;
    }
}

以防大家對 Stack不那麼熟悉，Peek是回傳Stack最後一個物件，Pop則是將最後一個物件移出來並回傳

我們儲存了一個溫度遞減的Stack (最高且還沒算完的溫度在最下面)

我們在迴圈中，會去依次檢查 Stack剩餘的物件，要是最上面的索引溫度小於當前溫度，就會移出這個索引，並計算差值。兩個可能會停下，一是Stack空了，二是最上面的索引代表的溫度不高於當前溫度。

所以儘管這個解法一眼看上去會是 O(n²)，但實際跑的次數應該不會有想像中的多(因為Stack是動態變動的)

結論

講到每日氣溫，就讓我想到前幾週台灣來寒流的溫度真的是冷到一個不行

連睡覺都會被冷醒…

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Daily Temperatures – LeetCode

一些隨機的LeetCode文章