Leetcode — 739. Daily Temperatures (中文)

問題連結: https://leetcode.com/problems/daily-temperatures/

給予一陣列T代表每天的溫度, 請回傳一個陣列紀錄當我們在某天的時候, 最快要幾天才能碰到比當天還溫暖的天氣, 若未來沒有任何一天會比當天還溫暖, 則就設要0天才能碰到

限制:

1. 溫度陣列長度會介於 [1, 30000]之間
2. 各溫度的範圍會介於[30, 100]之間

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

想法:

這篇文章, 我將會介紹四種不同的程式碼來看我們如何解這題

最簡單又直覺的解法就是用O(n²)來解這題, 當我們在Day i的時候, 我們可以從Day (i+1)往後找, 找到第一個比Day i 還熱的日子

以下為1002ms 的程式碼, 使用上述邏輯—

public int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] rst = new int[n];
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++) //find the first hot day
            {
                if(T[j]>T[i])
                {
                    rst[i] =j-i;
                    break;
                }
            }
        }
        return rst;
    }

那我們接下來想我們能否用O(n)來解這題

因為題目有提到每天的溫度有個範圍限制, 且範圍其實相對溫度陣列可能的長度相對小很多, 我們可以用一個額外的陣列map 來記錄各溫度是在哪天會出現, 也就是說 map[i]就會代表我們最近期是哪一天遇到溫度是i (而我們之所以可以認為是最近期是因為 若我們有兩天以上的溫度一樣, 後面碰到的日子會直接取代先前紀錄的日子, 因此map[i]永遠維持最近期碰過的日子)

因為溫度範圍是在30跟100之間, 若我們直接創一個長度為101的陣列就會浪費map[0]~map[29]的空間, 因此我們會創一個長度為71的陣列, 讓map[0]代表我們最近期碰到溫度為30度的日子

當我們在Day i的時候, 我們將會去搜尋整個map陣列中所有溫度大於今天溫度, 找到離今天最近的日子, 就會是我們最後的答案, 而因為我們想要找到的目標日都是在Day i之後的(找到在今天之前比今天還熱的日子也沒用), 因此我們將會從最後一天開始往回走訪整個溫度陣列

因為我們在每天都至多會走訪71次(假設每天都30度的話), 因此時間複雜度為O(71n), 也可寫成O(n)

以下為15ms的程式碼, 贏過66% —

public int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] rst = new int[n];
        int[] map = new int[71];
        for(int i=n-1;i>=0;i--)
        {
            int cur = T[i]-30; //today's temperature
            int minDay = n;
            for(int temp=cur+1;temp<=70;temp++)
            {
                if(map[temp]==0)
                    continue;
                minDay = Math.min(minDay, map[temp]);
            }
            map[cur] = i;
            if(minDay!=n)
                rst[i] = minDay-i;
        }
        return rst;
    }

而你可能發現這個也不能是最優解, 因為我們每次都需要幾乎搜尋整個map陣列來檢查我們在到今天之前, 有沒有遇過任何所有比當天溫度還高的溫度們

因此若我們把整個邏輯顛倒過來 — 原本是要找幫今天(Day i)找所有比今天還熱的未來日, 變成幫忙在Day i之前的日子們找看看是否Day i能成為這些過去幾天他們最快能碰到的熱天, 而如果過去的日子真的比今天還冷, 而且他們也目前還沒找到比他們還熱的天, 那Day i就會是他們最快能找到的熱天

我們可以用一種資料結構來儲存這些 "還沒找到未來比當天還溫暖日子"的日子們, 我們決定用Stack堆疊來儲存, 因為我們希望我們每每拿到的都是離Day i最近期的日子

以下為13ms的程式碼, 贏過86% —

public int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] rst = new int[n];
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<n;i++)
        {
            while(!stack.isEmpty() && T[i]> T[stack.peek()])
            {
                int indx = stack.pop();
                rst[indx] = i - indx;
            }
            stack.push(i);
        }
        return rst;
    }

介紹完三種方法了, 我們可以看到剛剛接連介紹的兩種O(n)解法都需要靠用額外O(n)空間才能讓原本 O(n²)的解法進步到O(n), 但我們最後一種方法其實連額外空間都不需要

程式邏輯:

這次要介紹的解法, 我們將從這篇文章最一開始介紹的O(n²)的程式碼中做修改, 用類似動態規劃的概念 — 我們將會用一些已知知識幫忙來找我們在今天最快要多久才能碰到比今天溫暖的一天

在原本的程式碼中, 我們從第一天走到最後一天, 幫每天Day i找 在這天之後的第一個比今天還熱的日子, 然而, 若我們先幫未來的日子們都找到他們最快要幾天就可以碰到比當天還熱的話, 那對於Day i來說, 我們其實也先幫它篩選好 "可能會比Day i"來說是熱天的日子們了

因為我們需要利用未來日子的結果來當作我們的已知知識, 我們要從最後一天走訪整個溫度陣列, 當我們在Day i的時候, 我們會把一開始會把變數j設為隔天(Day i+1), 目標就是讓j指到可能成為對今天來說是熱天的日子

下列為當我們比較今天溫度(T[i])跟未來日子溫度(T[j])時, 我們要做的動作:

1. 若Day j比Day i還溫暖, 代表我們已找到離今天最近的日天了, 幫rst[i]設為Day j和Day i的日子差後我們就可以結束這輪

因為我們從最後一天往前走訪陣列, 代表我們到Day i的時候已知對Day j來說, 它的最近期熱天是哪一天, 因此—

2. 若Day j比Day i還冷 且 我們當初在Day j 的時候就已經沒有找到比Day i還要熱的日子了, (也就是rst[j]=0), 代表未來也不可能有日子比Day i還溫暖的日子了

3. 若Day j比Day i還冷 且 我們當初在Day j有找到最靠近Day j且比它熱的日子, 代表這個日子可能也可以比Day i 還熱, 因此我們會讓j設為那天日子, 然後再次重複我們現在比較Day i 和Day j的動作

以下為 3ms 的程式碼, 贏過 99% —

public int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] rst = new int[n];
        for(int i=n-1;i>=0;i--)
        {
            int j = i+1;
            while(j<n)
            {
                if(T[j]>T[i])
                {
                    rst[i] =  j-i;
                    break;
                }
                //if T[j] is colder
                if(rst[j]==0) //impossible
                    break;
                j += rst[j]; //then jump to the day hotter than T[j]   
            }
        }
        return rst;
    }