Daily Temperatures
temperatures[i] 是第 i 天的温度。对于每一天，计算从这一天起要等多少天才会出现温度更高的一天。如果之后没有温度更高的日子，则计为 0。返回一个长度相同的数组，其中第 i 项表示第 i 天需要等待的天数。
函数
- temperaturesinteger-array
- 按顺序排列的每天的温度
- 返回值integer-array
- 对于每一天，距离更暖和的一天还有多少天；如果没有，则为 0
约束条件
1 ≤ temperatures.length ≤ 10430 ≤ temperatures[i] ≤ 100- 更暖意味着温度严格更高：温度相同的后一天不算。
示例
- 输入
- temperatures = [71, 69, 72, 70, 70, 75, 68]
- 输出
- [2, 1, 3, 2, 1, 0, 0]
- 解释
- 第 0 天（71）等待 2 天，等到 72。第 3 天（70）跳过第 4 天相等的 70，等待 2 天，等到 75。75 或 68 之后都没有更高的温度，所以它们的结果都是 0。
- 输入
- temperatures = [40, 50, 60]
- 输出
- [1, 1, 0]
- 解释
- 每天都比前一天暖和，所以前两天各等待 1 天，最后一天等待 0 天。
- 输入
- temperatures = [64, 60, 58, 61]
- 输出
- [0, 2, 1, 0]
- 解释
- 64 之后没有更暖的温度了，所以第 0 天得到 0，尽管之后的温度又升高了。第 1 天的温度是 60，它跳过较低的 58，等了 2 天才遇到 61。
进阶
温度只有 71 个可能值，从 30 到 100。如何通过一个以温度为索引的表，从右向左一次遍历就回答每一天的问题？代价是什么？
提示
逐个打开提示，每个都会多透露一点。
如果暖和的日子很少，从每天开始向后扫描，可能每天都要花费多达 10^4 步。换个方向：从左到右遍历所有天数，并保留那些仍在等待更暖和日子的天数。暖和的日子到来时，这些天数会怎样？
从最早的等待日到最新的等待日，温度不会越来越高：如果较新的某一天温度更高，它早就会成为较早那一天的答案了。因此，等待中的最冷日总是最近的一天，而栈恰好能按这个顺序保存它们。
保留一个由天数索引组成的栈。对于每个新的一天，当栈顶那天的气温比今天低时，就将它弹出，并把今天的索引减去它的索引，作为它的答案。然后将今天压入栈中。最后仍留在栈中的天数，其答案保持为 0。
题解
从每一天开始向前扫描会重复计算；如果温暖的日子很少，每次扫描都会一直进行到末尾。你可以只遍历一遍所有日子，让每个新日子回答它超过的较早日子的问题。仍在等待答案的日子放在一个栈中，栈中温度从底部到顶部始终不会升高，因此只需遍历一遍就能得到所有答案。
从每天开始向前扫描
结果正确，但无法在最大的测试中运行完毕
思路
对于第 i 天，检查第 i+1 天、第 i+2 天，依此类推，直到遇到第一个严格更暖的日子 j，然后停止。答案是 j-i；如果扫描到末尾，答案就是 0。按顺序扫描，遇到的第一个更暖的日子就是距离最近的那个。
如果 10^4 天的温度都相同，扫描就不会提前停止：大约需要 n²/2 = 5 × 10^7 次比较，而且第 1 天几乎会重复第 0 天已经扫描过的所有内容。
算法
- 创建一个全为 0 的答案数组，每天对应一个条目。
- 对于每天
i，从i+1开始扫描j，直到最后一天。 - 找到第一个满足
temperatures[j] > temperatures[i]的j时，存入j-i，并停止扫描。 - 返回答案数组；扫描时没有找到符合条件的值的日期，保留 0。
def dailyTemperatures(temperatures):
n = len(temperatures)
answer = [0] * n
for i in range(n):
for j in range(i + 1, n):
if temperatures[j] > temperatures[i]:
answer[i] = j - i # the first warmer day, so stop here
break
return answer等待天数的单调栈
思路
把还没有答案的日期作为索引保留在栈中。今天到来时，弹出所有比今天温度低、仍在等待的日期：今天是这些日期之后第一个更暖的日子，所以它们的答案是 today - day。然后把今天入栈。
只需要检查栈顶。只有当栈顶上方所有温度更低的日期都被弹出后，一个日期才会入栈，因此栈中的温度从底到顶永远不会升高。如果今天的温度不高于栈顶，那么它也不会高于下面的任何日期，此时就停止弹出。在第一个示例中，第 5 天（75）会弹出第 4、3、2 天，等待时间分别为 1、2、3；而第二个 70 从未弹出第一个 70，因为温度相等不算更暖。
每一天只入栈一次，最多弹出一次，因此弹出的总次数最多为 n：时间复杂度为 O(n)，即使某一天可能弹出多个日期。
算法
- 创建一个由 0 组成的答案数组，以及一个空的索引栈。
- 对于每一天
today，当栈顶那天的温度低于今天时，将它弹出，并将它的答案设为today减去它的索引。 - 将
today压入栈中。 - 循环结束后，仍留在栈中的那些天没有更暖和的日子，答案保持为 0。返回答案数组。
def dailyTemperatures(temperatures):
answer = [0] * len(temperatures)
waiting = [] # indices of days with no warmer day yet, colder toward the top
for today, temp in enumerate(temperatures):
# Today is the first warmer day for every colder day on top of the stack.
while waiting and temperatures[waiting[-1]] < temp:
day = waiting.pop()
answer[day] = today - day
waiting.append(today)
# Days still waiting never get a warmer day and keep their 0.
return answer
易错点和边界情况
- 遇到
>=时弹出，而不是遇到>时弹出。在第一个示例中，第 3 天会等待 1 天，直到第二个 70，而不是等待 2 天，直到 75。 - 压入温度而不是索引。这样你就无法计算距离，也无法确定要填写答案中的哪个位置。
- 需要使用
while时却使用了if。一个较暖的日子可以为多个等待的日子提供答案：在第一个示例中，75 可以为 3 天提供答案。 - 没有为仍在栈中的日子设置答案。它们的答案是 0；在 C 中，请使用
calloc分配答案，因为malloc分配的内存中会有垃圾值。 - 让正向扫描越过第一个更暖的日子。如果没有
break，它会记录最后一个更暖的日子。
常见问题3
每日温度的时间复杂度是多少？
单调栈解法的运行时间为 O(n)，额外空间为 O(n)，因为每天只会入栈一次，最多出栈一次。从每天开始向后扫描需要 O(n²) 时间，对于 10^4 天且没有更暖和的日子来说，大约需要 5 × 10^7 次比较。
每日气温问题可以不用栈来解决吗？
是的。从最后一天开始往前填写答案。对于第 i 天，从 j = i+1 开始；当第 j 天不比今天暖和时，跳到 j + answer[j]，也就是回答第 j 天的那一天。如果 answer[j] 是 0，第 i 天的答案也设为 0。这些跳转会跳过无法回答第 i 天的日期：时间复杂度为 O(n)，不需要额外内存。
每日气温与下一个更大元素有什么关系？
每个位置问的都是同一个问题：找到右侧下一个更大的值。Next Greater Element 返回这个值；Daily Temperatures 返回它相距多远，这就是为什么栈中存放的是索引。让栈在遇到更小的值时弹出，就能用同一个栈回答下一个更小元素的问题。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def dailyTemperatures(temperatures):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
temperatures = [71, 69, 72, 70, 70, 75, 68]
预期输出
[2, 1, 3, 2, 1, 0, 0]