739. 每日温度

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

示例 1:

1 2	>输入: temperatures = [73,74,75,71,69,72,76,73] >输出: [1,1,4,2,1,1,0,0]

示例 2:

1 2	>输入: temperatures = [30,40,50,60] >输出: [1,1,1,0]

示例 3:

1 2	>输入: temperatures = [30,60,90] >输出: [1,1,0]

这里需要使用到单调栈

递减栈（Decreasing Stack）是一种数据结构，通常用于解决与单调递减关系有关的问题。递减栈的特点是栈中的元素按照递减的顺序排列，即栈顶元素是最小的。

递减栈通常用于解决一些在遍历数组或序列时需要寻找某个元素的前/后第一个比它小的元素的问题。通过维护一个递减栈，我们可以在遍历数组的过程中，根据当前元素与栈顶元素的大小关系，得到有用的信息。

具体操作如下：

遍历整个数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是 递减栈 ，所以需要取出栈顶元素，由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离。

继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution(object):
    def dailyTemperatures(self, temperatures):
        #使用递减栈
        res = [0] * len(temperatures)
        stack = []

        for i in range(len(temperatures)):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                small = stack.pop()
                res[small] = i - small
            stack.append(i)

        return res