每日温度

根据往后 n 天的天气预报，计算每一天需要等待几天才会出现一次更高的气温，如果往后都没有更高的气温，则用 0 补位。

例如往后三天的气温是 [1,2,3] ， 则输出 [1,1,0]

方法一：暴力求解

具体方法

使用两次循环，第一层循环遍历到i位置时，从该位置的后面一个位置j = i+1开始遍历，如果找到一个大于位置i的温度，给位置res[i] 赋值为j-i;

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 每日温度
     * @param dailyTemperatures int整型一维数组 
     * @return int整型一维数组
     */
    public int[] temperatures (int[] dailyTemperatures) {
        // write code here
        int n = dailyTemperatures.length;
        int [] res =  new int[n];
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(dailyTemperatures[j]>dailyTemperatures[i]){
                    res[i] = j-i;
                    break;
                }

            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O$\mathrm{（}{n}^2\mathrm{）}（n^2）$，两层for循环
• 空间复杂度：O$\mathrm{（}1\mathrm{）}（1）$，无空间使用

方法二：单调栈

具体方法

方法一中需要多次遍历，有很多多余的运算，可以借助单调栈来求解本题，这里使用单调递降的单调栈，当前位置的数值如果小于栈顶，那就存入到栈中，如果大于栈中的元素，那就将栈顶弹出来

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 每日温度
     * @param dailyTemperatures int整型一维数组 
     * @return int整型一维数组
     */
    public int[] temperatures (int[] dailyTemperatures) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int n  = dailyTemperatures.length;
        int []res = new int[n];
        for(int i=0;i<n;i++){
            // 使用单调降栈 当当前元素大于栈顶的时候 需要处理
            while(!stack.isEmpty() && dailyTemperatures[stack.peek()]< dailyTemperatures[i]){
                //说明当前栈顶小于 当前，那就刚好
                int index = stack.pop();
                res[index] = i-index;
            }
            stack.push(i);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，$nn$ 是温度列表的长度。
• 空间复杂度：$O(n)O(n)$，$nn$ 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。