难度: Medium
请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 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]
示例 3:
输入: temperatures = [30,60,90] 输出: [1,1,0]
提示：
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100注意：本题与主站 739 题相同： https://leetcode-cn.com/problems/daily-temperatures/
运行时间: 100 ms
内存: 22.9 MB
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
length = len(temperatures)
ans = [0] * length
stack = []
for i in range(length):
temperature = temperatures[i]
while stack and temperature > temperatures[stack[-1]]:
prev_index = stack.pop()
ans[prev_index] = i - prev_index
stack.append(i)
return ans
此题解采用了单调栈的方法。单调栈用于维护一个元素索引的栈，索引对应的温度值是单调递减的。遍历温度列表，对于每一个温度，如果当前温度大于栈顶温度，说明找到了栈顶元素的第一个更高的温度，此时将栈顶元素索引弹出，并计算当前索引与栈顶索引的差值，作为答案数组对应位置的值。如果当前温度小于等于栈顶温度，或者栈为空，则把当前温度的索引压入栈。最后，栈中剩余的索引对应的温度值在右侧没有更高的温度值，答案数组默认已经初始化为0，因此不需要额外操作。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
length = len(temperatures) # 获取温度数组的长度
ans = [0] * length # 初始化答案数组，全部填充为0
stack = [] # 初始化一个栈，用来存储温度的索引
for i in range(length): # 遍历温度数组
temperature = temperatures[i] # 当前的温度
while stack and temperature > temperatures[stack[-1]]: # 当栈不为空且当前温度大于栈顶温度
prev_index = stack.pop() # 弹出栈顶元素，即之前的温度索引
ans[prev_index] = i - prev_index # 计算当前索引与之前索引的差，即等待天数
stack.append(i) # 将当前索引压入栈
return ans # 返回答案数组
单调栈中保持栈顶元素的温度单调递减的原因是为了正确地记录每个温度第一次出现更高温度的天数。栈中保存的是温度的索引，且对应的温度是递减的。当遇到一个新的温度比栈顶的温度高时，可以确定栈顶的温度在这一天后第一次遇到了更高的温度，因此可以计算两天的差值，然后更新答案数组。如果栈不是单调递减的，则无法保证这样的逻辑关系，会导致无法正确计算出正确的天数。
在题解中，如果当前温度等于栈顶温度，这种情况并没有特别处理，因为这并不影响结果。在算法逻辑中，我们主要关心的是找到一个'更高'的温度。等于栈顶温度的情况下，不弹出栈顶元素，因为我们还没有遇到一个更高的温度来更新之前温度的等待天数。当前温度的索引简单地被添加到栈中，这样，栈中可能会有连续的相同温度的索引，但这不会影响结果，因为我们只在遇到更高温度时才处理和更新答案数组。
代码中的while循环会在栈为空或当前温度不再大于栈顶温度的情况下结束。如果温度列表是单调递增的，栈的行为将是不断地将新的索引压入栈中，因为永远不会有一个当前温度小于或等于栈顶温度的情况。这意味着栈将持续增长，直到遍历完成。在这种情况下，由于没有任何元素能被弹出来更新答案数组，栈中的元素在最后都不会有更高温度的天数，答案数组的所有值将保持初始化的0。