【Hot100】739. 每日温度

739. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

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

题目理解：
对于输入 73，它需要 经过一天 才能等到温度的升高，也就是在第二天的时候，温度升高到 74 ，所以对应的结果是 1。

对于输入 74，它需要 经过一天 才能等到温度的升高，也就是在第三天的时候，温度升高到 75 ，所以对应的结果是 1。

对于输入 75，它经过 1 天后发现温度是 71，没有超过它，继续等，一直 等了四天，在第七天才等到温度的升高，温度升高到 76 ，所以对应的结果是 4 。

对于输入 71，它经过 1 天后发现温度是 69，没有超过它，继续等，一直 等了两天，在第六天才等到温度的升高，温度升高到 72 ，所以对应的结果是 2 。

对于输入 69，它 经过一天 后发现温度是 72，已经超过它，所以对应的结果是 1 。

对于输入 72，它 经过一天 后发现温度是 76，已经超过它，所以对应的结果是 1 。

对于输入 76，后续 没有温度 可以超过它，所以对应的结果是 0 。

对于输入 73，后续 没有温度 可以超过它，所以对应的结果是 0 。

想法：针对每个温度值 向后进行依次搜索 ，找到比当前温度更高的值，这是最容易想到的办法。

原理：是从左到右除了最后一个数其他所有的数都遍历一次，最后一个数据对应的结果肯定是 0，就不需要计算。

遍历的时候，每个数都去向后数，直到找到比它大的数，数的次数就是对应输出的值。

class Solution {
    
    public int[] dailyTemperatures(int[] temperatures) {
    
        int len = temperatures.length;
        int[] res = new int[len];
        for(int i=0;i<len;i++){
    
            int cur = temperatures[i];
            if(cur < 100){
    
                for(int j=i+1;j<len;j++){
    
                    if(temperatures[j] > cur){
    
                        res[i] = j-i;
                        break;
                    }
                }
            }
        }
        return res;

    }

}

用栈来解决：
递减栈 ：栈里只有递减元素。
遍历整个数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是 递减栈 ，所以需要取出栈顶元素，由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离。

继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来。

class Solution {
    
    public int[] dailyTemperatures(int[] T) {
    
        Stack<Integer> stack = new Stack<>();
        int length = T.length;
        int[] result = new int[length];

        for (int i = 0; i < length; i++) {
    
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
    
                int pre = stack.pop();
                result[pre] = i - pre;
            }
            stack.add(i);

        }
        return result;
    }

   
}