leetcode刷题记录（八十四）——739. 每日温度

（一）问题描述

739. 每日温度 - 力扣（LeetCode）739. 每日温度 - 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 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] <= 100https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-likedhttps://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 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

（二）解决思路

        使用栈来解决，但是栈里存放的不是元素的值本身，而是下标，方便定位元素进而算出相差的天数。

• 逐个遍历temperatures中的元素
• 如果栈为空，先将元素入栈
• 如果不为空，比较它和栈顶元素的大小，如果小于栈顶元素则入栈，大于栈顶元素则将栈顶元素出栈，此时遍历到的元素就是距离栈顶元素最近的高温天气，可知它距离栈顶元素天数为当前索引-栈顶元素。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> st = new Stack<Integer>();
        int[] ans = new int[temperatures.length];

        for(int i=0;i<temperatures.length;i++){
           while(!st.isEmpty()&&temperatures[i]>temperatures[st.peek()]){
                int prev=st.pop();
                ans[prev]=i-prev;
           }
           st.push(i);
        }
        return ans;
    }
}