题目描述:请根据每日 气温 列表 temperatures ,请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高,请在该位置用 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 <=
- 30 <= temperatures[i] <= 100
题目分析:这道题考察单调栈的知识,使用单调栈解决这道题很方便。首先,我们创建一个栈作为单调栈,因为题目要求的是升温的天数,而不是升温后的温度,因此栈中应该存储下标,而非温度。然后从左向右遍历每日温度,若栈为空或者当日温度小于等于栈顶温度则直接入栈。否则,若当日温度大于栈顶温度,说明栈顶元素的升温日已经找到了,则将栈顶元素出栈,计算其与当日相差的天数即可。 题解:执行用时: 32 ms 内存消耗: 47.8 MB class Solution { public int[] dailyTemperatures(int[] temperatures) { // 获取天数 int n = temperatures.length; // 结果数组 int[] res = new int[n]; // 单调栈 Stack<Integer> stack = new Stack<>(); // 循环遍历每日温度数组 for (int i = 0; i < n; ++i) { // 当栈非空 while (!stack.empty()) { // 获取栈顶元素值 int index = stack.peek(); // 如果当前温度 小于等于 栈顶温度 if (temperatures[i] <= temperatures[index]) { // 退出循环 break; } // 否则弹出栈顶元素 stack.pop(); // 并把日期差填入结果数组相应位置上 res[index] = i - index; } // 栈为空就把当前日期压入栈中 stack.push(i); } // 返回结果数组 return res; } }
|