739.每日温度.md

739.每日温度

题目

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，
给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

方法（单调栈）

题目的意思为：要我们对于数组中的每一个数，找到右边最近的比它大的那个数离它有多远

对于在数组中寻找左右两边最近的比它大或比它小的数的情况，我们可以使用单调栈来解决。

算法流程：
准备一个栈，然后遍历数组：

• 如果当前元素比栈顶元素小，那么直接入栈。

• 如果当前元素比栈顶元素大，那么不断地将栈顶元素弹出，直到当前元素比栈顶元素小为止，再将当前元素入栈。以让栈保持从栈底到栈顶从大到小的单调性。

• 每当栈中一个元素弹出时，说明让它弹出的那个元素就是它右边最近的比它大的元素。我们这时进行结算，它们之间的距离就是它们在数组中的位置（索引）之差。也正因为如此，为了方便，我们在将元素入栈出栈时，都针对的是它在数组中的索引，而不是它具体的值。

• 当遍历完所有元素后，如果栈中还有元素没有弹出，说明这些元素没有遇到右边比它大的元素，将结果数组中这些元素对应的位置处置0

代码

public int[] dailyTemperatures(int[] T) {
    int[] res = new int[T.length];
    Stack<Integer> stack = new Stack<>();
    for(int i = 0; i < T.length; i++){
        while(!stack.isEmpty() && T[i] > T[stack.peek()]){
            int index = stack.pop();
            res[index] = i - index;
        }
        stack.push(i);
    }
    while(!stack.isEmpty()){
        int index = stack.pop();
        res[index] = 0;
    }
    return res;
}