用 單調棧 來解 每日溫度變化 Daily Temperatures Leetcode #739 精選75題

Jonas Jaeken on Unsplash

題目敘述

題目會給定一個輸入陣列temperatures ，分別代表每一天的溫度。

請計算每一天還要再過幾天才會遇到更溫暖的日子，如果遇不到，則回填0。

請以陣列的形式返回答案。

題目的原文敘述

測試範例

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 <= 10^5

溫度陣列的長度介於 1 ~ 十萬。

• 30 <= temperatures[i] <= 100

每個陣列元素值介於30~100之間。

演算法 Monotone Stack 單調棧

維護一個遞減單調棧，每次推入溫度時，把前面比較小的溫度都pop出來，並且趁機計算兩者之間的索引差值，更新前面比較冷的那幾天再過幾天才會遇到更溫暖的日子。最後推入自己當下這天的索引值。

反覆迭代更新，掃描每一天的溫度，同時維護遞減單調棧。

如果某一天無解，也就是某一天之後不會遇到更溫暖的日子，則回填0。

程式碼 Monotone Stack 單調棧

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        size = len(temperatures)
        
        # waiting days of next warmer temperature
        waiting_days = [ 0 for _ in range(size) ]
        
        ## monotone decreasing stack to help us to find waiting days of next warmer temperature
        # first parameter is array index
        # second parameter is temperature
        stack = []
        
        for cur_idx, cur_t in enumerate(temperatures):
            
            # keep stack in decreasing order
            while stack and cur_t > stack[-1][1]:
                
                # get index and temperature of previous colder day
                prev_idx, prev_t = stack.pop()
                
                # update waiting days for previous colder day
                waiting_days[prev_idx] = cur_idx - prev_idx
            
            # add current index and current temperature into stack
            stack.append( (cur_idx, cur_t) )
            
            
        return waiting_days