739. 每日温度

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]

提示：
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

思路： 用单调递减队列来实现，求出右侧第一个比我大的值得索引，然后减去当前索引 把得到的值 放进数组返回即可

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        
        if(temperatures==null||temperatures.length==0) return temperatures;

        Stack<Integer> stack = new Stack<>();
        int[] result = new int[temperatures.length];
  
        for(int i = 0;i<temperatures.length;i++) {
            /**
            栈不为空 且 当前索引位的值大于栈顶索引位的值，
            那对栈顶索引来说就找到了右边第一个比自己大的咯
             */
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                // i - 栈顶索引
                result[stack.peek()] = i - stack.peek();
                //推出
                stack.pop();
            }
            //入栈
            stack.push(i);
        }
        return result;
    }
}

思路二：倒推法，因为最后一个温度是不会有比它高的温度出现的，所以就可以根据这个来倒推

    public int[] dailyTemperatures(int[] temperatures) {
        
        //普通边界判断
        if(temperatures==null||temperatures.length==0) return temperatures;

        int[] result = new int[temperatures.length];
        
        //可以确定最后一个温度是不会升高的，所以从倒数第二个开始倒推
        for(int i = temperatures.length-2;i >= 0;i--) {
            int j = i + 1;
            //循环只要能确定i位置下一个更高温度出现在几天后，就跳出while循环；i--
            while(true){
                //1.如果T[i] < T[j],那么result[i] = j - i 然后i--
                if(temperatures[i] < temperatures[j]) {
                   result[i] = j - i;
                   break;
                }
                //2.如果T[i] == T[j]
                if(temperatures[i] == temperatures[j]) {
                    //result[j]==0,说明右边没有比它大的了，俩人又是相等 那么 i 位置右边也一样 i--
                    if(result[j]==0){
                        result[i] = 0;
                        break;
                    }else {
                        //result[j]!=0 ,j索引位的比它第一个大的天数 + j和i的天数差, i--
                        result[i] = result[j] + (j - i);
                        break;
                    }
                }
                //3.如果T[i] > T[j]
                if(temperatures[i] > temperatures[j]) {
                    //result[j]==0, 就说明右边没有比j位置温度更高的了，i自然也一样
                    if(result[j]==0) {
                        result[i] = 0;
                        break;
                    }else {//右边有比j位置温度高的，就让j退回到哪里，然后再次给T[i] 比就好了
                        j = j + result[j];
                    }
                }
            }
            
        }
        return result;
    }

倒推代码优化版：

    public int[] dailyTemperatures(int[] temperatures) {
        
        //普通边界判断
        if(temperatures==null||temperatures.length==0) return temperatures;
 
        int[] result = new int[temperatures.length];
        
        //可以确定最后一个温度是不会升高的，所以从倒数第二个开始倒推
        for(int i = temperatures.length-2;i >= 0;i--) {
            int j = i + 1;
            //循环只要能确定i位置下一个更高温度出现在几天后，就跳出while循环；i--
            while(true){
                //1.如果T[i] < T[j],那么result[i] = j - i 然后i--
                if(temperatures[i] < temperatures[j]) {
                   result[i] = j - i;
                   break;
                }else if(result[j]==0) {//(T[i] == T[j] || T[i] > T[j]) && result[j]==0
                   result[i] = 0;
                   break;
                }
                //2. (T[i] == T[j] || T[i] > T[j]) && result[j]!=0
                //右边有比j位置温度高的，就让j退回到哪里，然后再次给T[i]比就好了
                j = j + result[j];
           }
        }
        return result;
    }