难度: Medium
给定一个整数数组 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]
示例 3:
输入: temperatures = [30,60,90] 输出: [1,1,0]
提示：
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100运行时间: 496 ms
内存: 19 MB
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
stack = []
ans = [0] * len(T)
for i in range(len(T)):
while stack and T[stack[-1]] < T[i]:
idx = stack.pop()
ans[idx] = i - idx
stack.append(i)
return ans
这个题解使用了单调栈的方法。我们维护一个单调递减的栈，栈中存储的是数组的下标。当遍历到当前元素时，如果栈顶元素对应的温度比当前温度低，则将栈顶元素弹出，并计算其与当前下标的差值，即为下一个更高温度出现的天数。重复这个过程直到栈为空或者栈顶元素对应的温度比当前温度高。最后将当前下标压入栈中。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
stack = [] # 维护一个单调递减的栈，存储元素下标
ans = [0] * len(T) # 初始化答案数组，默认值为0
for i in range(len(T)):
# 当栈不为空，且当前温度大于栈顶元素对应的温度时
while stack and T[stack[-1]] < T[i]:
idx = stack.pop() # 弹出栈顶元素的下标
ans[idx] = i - idx # 更新答案数组中对应位置的值
stack.append(i) # 将当前下标压入栈中
return ans # 返回最终的答案数组
单调栈被选用是因为它能有效地处理与顺序相关的问题，特别是在需要解决元素前后关系的问题时很有用。在这个题目中，我们需要找到每个温度后面第一个更高的温度。使用单调栈可以在一次遍历中完成这个任务，因为它可以在遇到一个需要解决的温度时立即进行处理。如果使用队列或普通列表，我们可能需要多次遍历数据或进行复杂的索引操作，这样会增加时间复杂度。
单调栈中的元素是按照温度的递减顺序排列的。这种顺序是必要的，因为我们需要找到每个元素后面第一个更高的温度。当遍历到一个新的温度时，如果它比栈顶的温度高，那么栈顶的温度就找到了它后面的第一个更高温度。通过维持这种递减顺序，我们可以保证每个被弹出的温度都正确地找到了其后的更高温度，从而有效地解决问题。
这种操作确保了每个元素在被处理时，其在栈中的位置正好位于它之前所有未找到更高温度的日期的最前面。当一个新的温度到来并且比栈顶温度高时，栈顶的日期就找到了它的更高温度。因此，这个日期可以从栈中被移除。由于每个元素在进入栈时都是因为没有找到更高的温度，而每次从栈中移除都是因为找到了更高的温度，这保证了每个日期只被压入和弹出一次，同时也保证了算法的效率。
在温度列表单调递减的极端情况下，由于没有任何一个温度会比前一个高，栈将会在每次迭代中接收新的下标，而不会有任何弹出操作直到遍历结束。这意味着栈的大小会增长到与输入列表的大小相同。但即使在这种情况下，每个元素仍然只被压入栈一次，并在最后一次迭代结束时集中弹出。因此，总体时间复杂度依然是O(n)，其中n是列表的长度。虽然空间复杂度可能在这种情况下达到最大，即O(n)，但这仍然是可接受的，因为我们需要额外的空间来存储栈。