LeetCode刷题【739】每日温度

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

题解

一样的，最直接的办法，遍历循环往后探测到一个比当天天温度高的。

而对于题中的描述，要求的是后面第一个比当前天气高的天数，换个说法，就是找后面的数据的单调递增栈的栈顶元素。

思路就出来了。

从后往前遍历，如果当前天的气温比栈定元素的气温高（或者等于），则持续对栈弹出操作。直到弹出到最后栈顶的天气是比当前天气高的。

那么此时的栈顶元素就是从当天开始往后找到的第一个比当前天温度高的那一天。

import java.util.Stack;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    private Stack<Integer> stack;

    public int[] dailyTemperatures(int[] temperatures) {
        stack = new Stack<>();
        int[] res = new int[temperatures.length];
        for (int i = temperatures.length-1; i >= 0; i--) {
            if (stack.isEmpty()){
                stack.push(i);
            }else{
                //把后面的比当前温度高的弹出去
                while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]){
                    stack.pop();
                }
                if (!stack.isEmpty()){
                    //此时栈顶的那个就是当前天数后面第一个比当前天温度高的
                    res[i] = stack.peek()-i;
                }
                stack.push(i);
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

这个思路对于我而言是比较显而易见的。其实也可以从前面开始正向遍历。具体思路和另外一题LeetCode刷题【503】下一个更大元素 II一致。

正向遍历，存递减栈数据，判断，如果当前值小于等于栈顶值，直接加入，如果大于栈顶值，挨个从栈顶弹出比当前天的温度小的天，并给他们赋值，他们后面的第一个比他们的温度高是当前这一天。