題目敘述
題目會給定一個輸入陣列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
