题目地址

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] 范围内的整数。

思路

1. 暴力法，如果后一个元素值比当前小，则遍历后面的元素，直到找到比当前值大的元素。
2. 如果后一个元素值比当前小，把下标存储在栈里，否则一直出栈，当前下标减栈存储的下标就是栈存储下标的那天需要等待的天数。
   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;
    }
}