leetcode hot 100

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(n²)

空间复杂度：除了用来存储结果的数组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)