付費限定文章

用 單調棧 來解 每日溫度變化 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 單調棧