739.每日温度

题目

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/daily-temperatures
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解思路

1>源代码

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        ans = [0] * len(T)
        stack = []
        for i in range(len(T)):
            temperature = T[i]
            while(stack and temperature > T[stack[-1]]):
                index = stack.pop()
                ans[index] = i - index
            stack.append(i)
        return ans

2>算法介绍

刚拿到这道题的时候，我第一反应就是使用暴力算法，既然我要寻找某元素后面第一个比他大的元素，我直接写双重循环肯定是最直观的，当然也是效率较低的。

在题目的解析中我看到了一种算法——[单调栈]。以输入为 [73, 74, 75, 71, 69, 72, 76, 73] 为例，申请ans列表，长度与输入列表的长度相等，同时维护一个栈stack。

1. stack = (0): 将第一个元素的下标压栈；
2. 由于74>73, 则stack = (1), ans[0] = 1: 由于T[1] > T[stack[-1]]，则将栈顶元素出栈(即0出栈)，构造ans[0] = 1 - 0；
3. 由于75>74, 则stack = (2), ans[1] = 1: 由于T[2] > T[stack[-1]]，则将栈顶元素出栈(即1出栈)，构造ans[1] = 2 - 1；
4. 由于71 < 75，则stack = (2, 3)
5. 由于69 < 71，则stack = (2, 3, 4)
6. 由于72>69, 72>71，则stack = (2, 5), ans[3] = 2, ans[4] = 1: 由于T[5] > T[stack[-1]]，则将栈顶元素出栈(即4出栈)，构造ans[4] = 5 - 4；由于T[5] > T[stack[-1]]，则将栈顶元素出栈(即3出栈)，构造ans[3] = 5 - 3；
7. 由于76>72，76>75, 则stack = (6)，ans[2] = 4, ans[5] = 1;
8. 由于73<76,则stack = (6, 7), ans不变

最终 ans = [1, 1, 4, 2, 1, 1, 0, 0]

以上就是以 [73, 74, 75, 71, 69, 72, 76, 73] 为输入的算法全过程，我们只需按照这个过程构造代码即可。