leetcode hot 100 - 739. 每日温度

739. 每日温度

题目描述

请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

思路一:暴力双循环

从当前元素往后找,找到第一个大于自己的元素,保存下标之差

 1 class Solution {
 2     public int[] dailyTemperatures(int[] T) {
 3         // 暴力双重循环
 4         int len = T.length;
 5         int[] arr = new int[len];
 6         for(int i = 0; i < len-1; i++){
 7             for(int j = i+1; j < len; j++){  // 跳过温度小于等于T[i]的
 8                if(T[i] < T[j]){
 9                     arr[i] = j - i;
10                     break;
11                }
12             }
13         }
14         return arr;
15     }
16 }

leeetcode 执行用时:1248 ms > 5.01%, 内存消耗:46.7 MB > 45.47%

复杂度分析:

时间复杂度:有两个for循环,最坏时间复杂度为O(n2)

空间复杂度:除了用来存储结果的数组arr[], 其他的空间都是常量级别的,所以空间复杂度为O(1)

思路二:利用递减栈

思路分析:https://leetcode-cn.com/problems/daily-temperatures/solution/leetcode-tu-jie-739mei-ri-wen-du-by-misterbooo/(强力推荐)

遍历数组,判断当前元素与栈顶下标对应的元素的大小,如果如果当前元素大于栈顶下标对应的元素,弹出栈顶下标,计算当前元素和栈顶下标之差,保存在栈顶下标的结果数组中,否则将当前元素的下标也压入栈中,始终保持从栈底到栈顶下标对应的元素是递减的。

 1 class Solution {
 2     public int[] dailyTemperatures(int[] T) {
 3         // 递减栈
 4         int len = T.length;
 5         int[] res = new int[len];
 6         Stack<Integer> stack = new Stack<Integer>();
 7 
 8         // 遍历数组
 9         for(int i = 0; i < len; i++){
10             // 如果栈不为空且栈顶下标对应的元素小于当前元素,持续弹栈,计算下标之差
11             while(!stack.isEmpty() && T[i] > T[stack.peek()]){
12                 int index = stack.pop();
13                 res[index] = i - index;
14             }
15 
16             // 最后将当前元素的下标压入栈中
17             stack.push(i);
18         }
19         return res;
20     }
21 }

leetcode 执行用时:22 ms > 51.39%, 内存消耗:46.7 MB > 38.37%, 根据这个运行时间来看,确实是快了几十倍

复杂度分析:

时间复杂度:只遍历了一次数组,所以时间复杂度为O(n)

空间复杂度:需要一个栈,栈的最大大小可能为数组大小,所以空间复杂度为O(n)

上一篇:P3565 [POI2014]HOT-Hotels


下一篇:IDEA push rejected原因与解决