入口
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/daily-temperatures/description/
题目描述
给定一个整数数组
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
方法一:暴力法
该算法使用两个嵌套循环,对于每一天,它都会遍历后续的天数来查找第一个温度升高的日子。测试集足够大时,此方法在leetcode中会超出时间限制。
Java实例
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length]; // 用于存储结果的数组
for (int i = 0; i < temperatures.length; i++) {
int temp = 0; // 用于记录等待的天数
for (int j = i+1; j < temperatures.length; j++) {
if (temperatures[j] > temperatures[i]) {
temp = j - i; // 如果找到升高的温度,则计算等待的天数
break; // 跳出内层循环,因为已经找到了升高的温度
}
}
res[i] = temp; // 将等待的天数存储在结果数组中
}
return res; // 返回结果数组
}
}
复杂度分析
- 时间复杂度:O(n^2),其中 n 是温度数组的长度。因为对于每一天,最坏情况下需要遍历数组的其余部分来找到温度升高的日子。
- 空间复杂度:O(1),只使用了常量级的额外空间。
方法二:暴力法改进-辅助数组
该方法是暴力法的改进方法,其核心思想是利用辅助数组 next 来记录每个温度后面出现的更高温度的索引位置,从而避免了嵌套循环。
辅助数组 next: 这个数组的索引表示温度值,数组中的值表示该温度值在原数组中出现的索引位置。初始化为最大值,表示当前温度后面没有更高的温度。
逆序遍历原数组: 从数组末尾开始向前遍历,这是因为我们需要找的是每个温度后面第一次出现的更高温度,逆序遍历可以确保我们从后往前找到更高温度。
查找更高温度的索引: 对于每个温度,我们不需要遍历其后面的所有温度,而是直接查找辅助数组 next 中大于当前温度的最小索引值,即下一个更高温度的索引。
通过这种方法,我们只需要一次遍历原数组,时间复杂度为 O(n),大大提高了效率。
Java示例
public static int[] dailyTemperatures(int[] temperatures) {
int length = temperatures.length;
int[] ans = new int[length]; // 用于存储结果的数组
int[] next = new int[101]; // 辅助数组,用于存储下一个更暖和的温度的索引
// 初始化辅助数组为最大值,表示没有更暖和的温度
Arrays.fill(next, Integer.MAX_VALUE);
// 从数组末尾开始遍历
for (int i = length - 1; i >= 0; --i) {
int warmerIndex = Integer.MAX_VALUE; // 用于记录下一个更暖和的温度的索引, 初始值设为 Integer.MAX_VALUE,表示初始情况下没有更高温度。
// 遍历当前温度之后的所有可能温度,最高温度不会超过 100
for (int t = temperatures[i] + 1; t <= 100; ++t) {
if (next[t] < warmerIndex) { //找到了比当前温度更高的温度,并且它的索引比之前记录的更高温度索引还要小,就更新 warmerIndex。这样,warmerIndex 就始终记录着当前温度后面第一次出现更高温度的索引位置。
warmerIndex = next[t]; // 找到下一个更暖和的温度的索引
}
}
// 如果找到了更暖和的温度,则计算等待的天数
if (warmerIndex < Integer.MAX_VALUE) {
ans[i] = warmerIndex - i;
}
// 更新辅助数组,将当前温度的索引存储在相应的位置
next[temperatures[i]] = i;
}
return ans; // 返回结果数组
}
复杂度分析
- 时间复杂度:O(nm),其中 n 是温度列表的长度,m 是数组 next 的长度,在本题中温度不超过 100,所以 m 的值为 100。反向遍历温度列表一遍,对于温度列表中的每个值,都要遍历数组 next 一遍。
- 空间复杂度:O(m),其中 m 是数组 next 的长度。除了返回值以外,需要维护长度为 m 的数组 next 记录每个温度第一次出现的下标位置。
方法三:单调栈
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
// 创建一个数组用于存储结果,长度与温度数组相同
int[] ans = new int[temperatures.length];
// 创建一个栈用于存储温度数组的索引
Deque<Integer> stack = new LinkedList<>();
// 遍历温度数组
for(int i = 0; i < temperatures.length; ++i){
// 如果栈不为空并且当前温度大于栈顶温度
while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
// 弹出栈顶索引,计算等待天数并记录到结果数组中
int preIndex = stack.pop();
ans[preIndex] = i - preIndex;
}
// 将当前索引入栈
stack.push(i);
}
// 返回结果数组
return ans;
}
}
时间复杂度:O(n),其中 nnn 是温度列表的长度。正向遍历温度列表一遍,对于温度列表中的每个下标,最多有一次进栈和出栈的操作。
空间复杂度:O(n)O,其中 nnn 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。
单调栈练习题
leetcode496.下一个更大元素1
leetcode901.股票价格跨度
leetcode42.接雨水
leetcode84.柱状图中最大的矩形