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

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]

输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]

输出: [1,1,1,0]

解题思路

常日在一维数组，要探求任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

单调栈的实质是空间换韶光，由于在遍历的过程中须要用一个栈来记录右边第一个比当前元素高的元素，优点是只须要遍历一次，因此韶光繁芜度为O(n)。

利用单调栈紧张有三个判断条件。

当前遍历的元素T[i]小于栈顶元素T[st.top()]的情形当前遍历的元素T[i]即是栈顶元素T[st.top()]的情形当前遍历的元素T[i]大于栈顶元素T[st.top()]的情形

把这三种情形剖析清楚了，也就理解透彻了。

图解示例

以上述示例一举例，首先先将第一个遍历元素加入单调栈：

加入T[1] = 74，由于T[1] > T[0]（当前遍历的元素T[i]大于栈顶元素T[st.top()]的情形），而我们要保持一个递增单调栈（从栈头到栈底），以是将T[0]弹出，T[1]加入，此时result数组可以记录了，result[0] = 1，即T[0]右面第一个比T[0]大的元素是T[1]。

加入T[2]，同理，T[1]弹出

加入T[3]，T[3] < T[2] （当前遍历的元素T[i]小于栈顶元素T[st.top()]的情形），加T[3]加入单调栈。

加入T[4]，T[4] == T[3] （当前遍历的元素T[i]即是栈顶元素T[st.top()]的情形），此时依然要加入栈，由于我们哀求的是右面第一个大于本元素的位置！

加入T[5]，T[5] > T[4] （当前遍历的元素T[i]大于栈顶元素T[st.top()]的情形），将T[4]弹出，同时打算间隔，更新result。

T[4]弹出之后， T[5] > T[3] （当前遍历的元素T[i]大于栈顶元素T[st.top()]的情形），将T[3]连续弹出，同时打算间隔，更新result。

直到创造T[5]小于T[st.top()]，终止弹出，将T[5]加入单调栈。

加入T[6]，同理，须要将栈里的T[5]，T[2]弹出。

此时栈里只剩下了T[6]，加入T[7]， T[7] < T[6] 直接入栈，这便是末了的情形，result数组也更新完了。

把稳末了创造没符合哀求的，result[6] , result[7]没有做相应的更新。
实在定义result数组的时候，就该当直接初始化为0，如果result没有更新，解释这个元素右面没有更大的了，也便是为0。

代码实现

class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: answer = [0]len(temperatures) stack = [0] for i in range(1,len(temperatures)): # 情形一和情形二 if temperatures[i]<=temperatures[stack[-1]]: stack.append(i) # 情形三 else: while len(stack) != 0 and temperatures[i]>temperatures[stack[-1]]: answer[stack[-1]]=i-stack[-1] stack.pop() stack.append(i) return answer