算法题之每日温度

每日温度

给定一个整数数组 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 <= 105
• 30 <= temperatures[i] <= 100

解题思路一：反向遍历

一看到题目，要找到下一个更高的温度，首先马上想到可以反向遍历。因为倒序的时候， 可以保证，如果有比当前温度大的下一个温度，一定会在遍历过的元素里。最重要的是，我们需要记录下来已经遍历过的元素。

然后我们看数组的元素的规律，温度的范围在30到100之间 。所以，我们可以维护一个101长度的数组next，温度为30至100度，作为数组的下标，元素设置为数组temperatures的下标。

• 维护的数组next，我们初始化元素值为Integer.MAX_VALUE
• 反向遍历数组temperatures，设置当前温度的next元素值为数组temperatures的下标
• 以当前温度+1的位置开始，正向遍历数组next，找到元素值小于Integer.MAX_VALUE的值；这个值就是temperatures的下标，然后从这些元素值中找到最小下标的那个，即为最近的下一个更高的温度

具体代码如下所示：

class Solution {public int[] dailyTemperatures(int[] temperatures) {int [] ans = new int[temperatures.length];int [] next = new int[101];Arrays.fill(next, Integer.MAX_VALUE);for (int i = temperatures.length - 1; i >= 0; i--) {int temperature = temperatures[i];ans[i] = 0;next[temperature] = i;int nextTemperatureIndex = Integer.MAX_VALUE;for (int j = temperature + 1; j < 101; j++) {if (next[j] < nextTemperatureIndex) {                    nextTemperatureIndex = next[j];}}if (nextTemperatureIndex < Integer.MAX_VALUE) {ans[i] = nextTemperatureIndex - i;}}return ans;}
}

 时间复杂度

• 时间复杂度：，其中n为数组temperatures的长度，m是数组next的长度。我们需要反向遍历一遍temperatures，并且遍历一遍数组next。
• 空间复杂度：，其中m 是数组next的长度。

 解题思路二：单调栈

在上面的方法中，我们是通过反向遍历数组temperatures，然后再在额外的数组next中找到最小下标的。那么我们可以换一种数据结构存储温度的下标，提高效率么？

首先，我们来看，如果正向地遍历数组temperatures

1. 遍历第1个元素的时候，我们记录下来下标0
2. 遍历第2个元素，我们比较第temperatures[0]和temperatures[1]
3. 如果temperatures[1]比temperatures[0]大，那么答案ans[0]= 1 - 0 = 1，并且我们就不用记录下标0了，转而记录下标1
4. 如果temperatures[0]比temperatures[1]大，那么不能确定答案，并且我们还要记录下标1，然后继续下后面遍历，如果能找到下标i（i > 1），依次和下标1、下标0的温度值比较
5. 如果temperatures[i]比temperatures[1]大，ans[1] = i - 1，并且我们移除记录的下标1；然后和下标0比较，具体类似步骤3、4

按照上面的步骤操作，我们会发现，可以额外用一个栈来记录下标，并且记录的下标对应的温度值，从栈底到栈顶，是依次递减的。每次遍历发现，当前遍历的温度值大于栈内下标对应的温度值时，可以依次弹栈并记录结果。具体代码如下所示：

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] ans = new int[temperatures.length];Deque<Integer> stack = new LinkedList<Integer>();// Stack<Integer> stack = new Stack<>();for(int i = 0; i < temperatures.length; i++){while(stack.isEmpty() == false && temperatures[stack.peek()] < temperatures[i]){int pre = stack.pop();ans[pre] = i - pre;}stack.push(i);}return ans;}
}

 时间复杂度

• 时间复杂度：，我们需要正向遍历一遍temperatures，并且每个下标出入栈只有一次。
• 空间复杂度：，需要使用栈，最坏的情况下为n。

在实际使用中，发现使用Stack的效率较低，时间复杂度甚至高于反向遍历；当我们使用LinkedList的时候，效率是正常的。如果有兴趣，可以看看Stack和LinkedList的源码分别是怎么实现出栈入栈的。