739. 每日温度

题目链接：https://leetcode-cn.com/problems/daily-temperatures/
难度：中等

描述：
给定一个整数数组temperatures，表示每天的温度，返回一个数组answer，其中answer[i]是指在第i天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用0来代替。

提示：
数组长度：[1, 100000]
温度范围：[30, 100]

题解

思路：
维护一个单调递减栈。遍历整个数组，当当前温度大于栈顶温度时，依次弹出栈顶元素，直到栈顶温度小于当前温度。然后将下标差填到answer中

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        length = len(temperatures)
        ret = [0] * length
        stk = []
        for i in range(length):
            while stk and temperatures[stk[-1]] < temperatures[i]:
                temp = stk.pop()
                ret[temp] = i - temp
            stk.append(i)
        return ret