Skip to content

LeetCode: 739-Daily Temperatures 解題紀錄

Last Updated on 2022-12-18 by Clay

題目

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.

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]

Constraints:

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

題目給定一串代表每天溫度的數值陣列 temperatures,我們要另外儲存一個新的陣列,陣列中 i 的位置代表 temperatures[i] 的溫度隔幾天後會遇到更高的溫度;如果無論幾天後都沒有更高的溫度,則儲存 0。


解題紀錄

反向走訪

解這題的一個訣竅是反著走。最後一天的溫度一定沒有之後比它更高的溫度,所以紀錄為 0。之後,如果倒數第二天比最後一天的溫度低,則紀錄為 1......

總之,當我們要找一個溫度更高的日子時,一開始當然是直接跟當前位置的後一天比;然而若是後一天沒有比較高的溫度,則直接從後一天找到溫度更高日子的時間差,直接移動到比後一天溫度更高的日子去比較

而這件事,我們會很理所當然地在反著走過來的時候做完,我們會知道比後一天溫度更高的第一個日子在哪裡,直接去比較那天就可以省下了中間很多無意義的比較過程。


反向走訪 複雜度

Time ComplexityO(n)
Space ComplexityO(n)


C++ 範例程式碼

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // Init
        vector<int> results(temperatures.size(), 0);

        // Find the larger point at the left side
        for (int i=temperatures.size()-2; i>=0; --i) {
            int j = i + 1;
            int steps = 1;
            bool isFound = false;

            // If `j` not out of boundary that we can explore
            while (j < temperatures.size()) {
                if (temperatures[i] >= temperatures[j]) {
                    if (results[j]) {
                        steps += results[j];
                        j += results[j];
                    }
                    else {
                        break;
                    }
                }
                else {
                    isFound = true;
                    break;
                }
            }

            if (isFound) {
                results[i] = steps;
            }
        }
        
        return results;
    }
};



Python 範例程式碼

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # Init
        results = [0] * len(temperatures)

        # Find the larger point at the left side
        for i in range(len(temperatures)-2, -1, -1):
            j = i + 1
            steps = 1
            isFound = False

            # If `j` not out of boundary that we can explore
            while j < len(temperatures):
                if temperatures[i] >= temperatures[j]:
                    if results[j]:
                        steps += results[j]
                        j += results[j]
                    else:
                        break
                else:
                    isFound = True
                    break

            if isFound:
                results[i] = steps
        
        return results

References


Read More

Leave a Reply取消回覆

Exit mobile version