题目：https://leetcode-cn.com/problems/daily-temperatures/
请根据每日气温列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

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

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

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

方法一：暴力解法(笨)

public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] temp=new int[len];
        for(int i=0;i<len;i++) {
            int n=0;
            for(int j=i+1;j<len;j++) {
                //如果匹配到大于当天的，就把相差的天数放入返回的数组，并跳出循环
                if(temperatures[i]<temperatures[j]) {
                    temp[i] = j-i;
                    break;
                }                
            }           
        }
        return temp;
    }

方法二：暴力解法的改进(减少重复遍历次数)

我们要找到更加快速的方法，在这道题中也就是要减少遍历的次数。遍历一次数组中所有的值应该是少不了的，因为至少数组中每个值都需要计算一遍，所以时间复杂度肯定大于 O(n)。关键是要减少为每个数寻找值遍历次数。

👆上图中绿色部分区域会给多次遍历，如果我们能减少这部分区域的遍历次数，就能整体提高运算效率。

如果我们先从计算右边，那么我们计算过的位置就不需要重复计算。当前我们需要计算 75 位置，然后向右遍历到 71，因为我们已经计算好了 71 位置对应的值为 2，那么我们就可以直接跳 2 位再进行比较，利用了已经有的结果，减少了遍历的次数。

public int[] dailyTemperatures(int[] T) {
    int length = T.length;
    int[] result = new int[length];
    //从右向左遍历
    for (int i = length - 2; i >= 0; i--) {
        // j+= result[j]是利用已经有的结果进行跳跃
        for (int j = i + 1; j < length; j+= result[j]) {
            if (T[j] > T[i]) {
                result[i] = j - i;
                break;
            }            
            else if (result[j] == 0) { //遇到0表示后面不会有更大的值，那当然当前值就应该也为0
                result[i] = 0;
                break;
            }
        }
    }
    return result;
}

方法三：单调栈

用一个单调栈存储下标：
从栈底到栈顶的下标对应的温度依次递减（即该栈是升序的）
如果下标还在单调栈内，说明还没找到比这个下标对应温度更高的下标

演示：

算法：正向遍历温度列表

• 对于温度列表中的每个元素 temperatures[i]，如果栈为空，则直接将 i 进栈

• 如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 temperatures[prevIndex]和当前温度 temperatures[i]

  • 如果 temperatures[i] > temperatures[prevIndex]，说明遍历到的温度大于栈顶下标对应的温度，则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex

  • 否则继续重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈

    public int[] dailyTemperatures(int[] temperatures) {
       int length = temperatures.length;
       int[] ans = new int[length];  //存储结果的数组   
       Deque<Integer> stack = new LinkedList<Integer>();  
       for (int i = 0; i < length; i++) {
           int temperature = temperatures[i];
           while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
               int prevIndex = stack.pop();
               ans[prevIndex] = i - prevIndex;
           }
           stack.push(i);
       }
       return ans;
    }