LC739. 每日温度

题目描述

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

题目解析

题目在说什么

这道题给你一个每天温度列表，比如 [73, 74, 75, 71, 69, 72, 76, 73]。你需要为每一天算出一个数字：从这一天开始，要等多少天，温度才会比这一天高。如果永远等不到，就填 0。

举个例子：

• 第1天73度：第二天就变成74度，比73高，所以等1天。
• 第3天75度：后面连续几天（71、69、72）都比75低，直到第7天76度才超过，所以等了4天。
• 最后一天73度：后面没日子了，永远等不到，填0。

所以输出就是 [1, 1, 4, 2, 1, 1, 0, 0]。

思路是怎么来的

你可能会想：最笨的办法就是每天往后看，一个个找比它大的数。比如第1天，往后看第2天就找到了；第3天要往后看4次。如果列表有30000天，最坏情况可能要看几亿次，太慢了。

能不能聪明一点？比如我们一边往后走，一边记下那些“还没找到更高温度的日子”。哪天遇到一个高温，就回头告诉之前那些“等着的日子”：你们等的就是今天。

这就像排队买奶茶：前面的人一直在等，突然来了一个更高的人（温度更高），前面的人就可以说“我等的就是你”，然后离开队伍。而新来的人如果不够高，就继续排队等着。

这个“排队”在算法里就叫栈。我们用一个栈来存放“还在等更高温度的日子”的下标。栈里的温度从底到顶是越来越低的（单调递增栈），因为温度低的日子先来，温度高的日子后来，但后来者如果不够高，就继续待在栈顶。

具体做法：

• 从左到右遍历每一天的温度。
• 对于每一天的温度，看看栈顶（最后一个还在等的日子）的温度是不是比它小。如果是，说明栈顶的日子等到了今天，就可以算出它等了几天（今天下标减去它的下标），然后把它从栈里移除。
• 重复这个步骤，直到栈顶温度比今天高或者栈空了。
• 然后把今天的下标也放进栈里，因为它也要等未来的更高温度。

这样每个日子只进栈一次、出栈一次，非常高效。

代码逐步拆解

参考代码（Java）如下，我们一句一句看：

Stack<Integer> stack = new Stack<>();
int[] res = new int[temperatures.length];

• 创建一个栈，用来存放下标（不是温度本身，因为我们需要下标算天数）。
• 创建一个结果数组，长度和温度列表一样，初始全是0。

for (int i = 0; i < temperatures.length; i++) {

• 从第0天开始，一天一天往后看。

while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {

• 只要栈不为空，并且今天的温度比栈顶那个日子的温度高，就说明栈顶的日子等到了今天。
• stack.peek() 是看看栈顶元素（下标），但不移除它。

int preIndex = stack.pop();
res[preIndex] = i - preIndex;

• pop() 把栈顶下标取出来并移除。