面试算法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;}
}