题目地址
https://leetcode-cn.com/problems/daily-temperatures/
题目描述
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
思路
- 暴力法，如果后一个元素值比当前小，则遍历后面的元素，直到找到比当前值大的元素。
- 如果后一个元素值比当前小，把下标存储在栈里，否则一直出栈，当前下标减栈存储的下标就是栈存储下标的那天需要等待的天数。
PS：存下标，因为知道下标就能查到温度，就相当于存了下标和温度。
题解
/**
* @Author: vividzcs
* @Date: 2021/3/2 10:40 上午
*/
public class DailyTemperatures {
public static void main(String[] args) {
int[] t = {73, 74, 75, 71, 69, 72, 76, 73};
int[] result = dailyTemperatures(t);
System.out.println(Arrays.toString(result));
result = dailyTemperaturesV2(t);
System.out.println(Arrays.toString(result));
}
/**
* 执行用时： 15 ms , 在所有 Java 提交中击败了 90.34% 的用户
* 内存消耗： 47 MB , 在所有 Java 提交中击败了 11.40% 的用户
*/
private static int[] dailyTemperaturesV2(int[] t) {
int len = t.length;
int[] result = new int[len];
if (len < 1) {
return result;
}
LinkedList<Integer> stack = new LinkedList<>();
for (int i=0; i<len; i++) {
int current = t[i];
while (!stack.isEmpty() && (current > t[stack.peek()])) {
int tmp = stack.poll();
result[tmp] = i - tmp;
}
stack.addFirst(i);
}
return result;
}
/**
* 执行用时： 1406 ms , 在所有 Java 提交中击败了 9.78% 的用户
* 内存消耗： 46.4 MB , 在所有 Java 提交中击败了 85.78%的用户
*/
private static int[] dailyTemperatures(int[] t) {
int len = t.length;
int[] result = new int[len];
if (len < 1) {
return result;
}
for (int i=0; i<len; i++) {
for (int j=i+1; j<len; j++) {
if (t[j] > t[i]) {
result[i] = j - i;
break;
}
}
}
return result;
}
}
