面试算法38：每日温度

题目

输入一个数组，它的每个数字是某天的温度。请计算每天需要等几天才会出现更高的温度。例如，如果输入数组[35，31，33，36，34]，那么输出为[3，1，1，0，0]。由于第1天的温度是35℃，要等3天才会出现更高的温度36℃，因此对应的输出为3。第4天的温度是36℃，后面没有更高的温度，它对应的输出是0。其他的以此类推。

分析

用一个栈保存每天的温度在数组中的下标。每次从数组中读取一个温度，然后将其与栈中保存的温度（根据下标可以得到温度）进行比较。如果当前温度比位于栈顶的温度高，那么就能知道位于栈顶那一天需要等待几天才会出现更高的温度。然后出栈1次，将当前温度与下一个位于栈顶的温度进行比较。如果栈中已经没有比当前温度低的温度，则将当前温度在数组中的下标入栈。

解

public class Test {
    public static void main(String[] args) {
        int[] tokens = {35, 31, 33, 36, 34};
        int[] result = dailyTemperatures(tokens);
        for (int res : result) {
            System.out.println(res);
        }
    }

    public static int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.empty() && temperatures[i] > temperatures[stack.peek()]) {
                int prev = stack.pop();
                result[prev] = i - prev;
            }

            stack.push(i);
        }

        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24