面试热题（每日温度）

小鱼儿 2023-10-14 20:06 3阅读 0赞

> 请根据每日 `气温` 列表 `temperatures` ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 `0` 来代替。
> 
>     输入: temperatures= [73,74,75,71,69,72,76,73]输出: [1,1,4,2,1,1,0,0]

每日温度是一道很典型的单调栈的问题，就是求下一个最大\*\*\*\*，下面先列出单调栈的模板

public int[] humdrum3tack(int[] nums) {
        int n = nums.length;
        // 存放答案的数组
        int[] res = new int[n];
        Stack<Integer> s = new Stack<>(); 
        // 倒着往栈里放   如果是环状，则使用取模运算进行绕环
        for (int i = n - 1; i >= 0; i--) {
            // 判定个子高矮
            while (!s.isEmpty() && s.peek() <= nums[i]) {
                // 把小于当前元素的栈中元素进行弹栈
                s.pop();
            }
            //如果栈中没元素，则后面没有比自己大的值，如果有，则是栈顶元素
            res[i] = s.isEmpty() ? -1 : s.peek();
            s.push(nums[i]);
        }
        return res;

下面利用图进行说明：

![67fd757fef02477fb38b12ce1f4f001c.png][]

单调栈又是什么什么原理呢？

![a951ae7103eb4eab9ad43988e688746d.png][]

入队的时候不断的和栈顶进行比较，小于入栈元素的直接进行出栈，如果入栈的时候栈为空，说明当前元素后面没有比当前元素大的值了

public int[] dailyTemperatures(int[] temperatures) {
          //对 入参进行判断
          if(temperatures==null||temperatures.length==0);
          int n=temperatures.length;
          Stack<Pair> stack=new Stack<>();
          //用来维护结果的结果数组
          int[] res=new int[n];
          //单调栈一般都是从后往前比遍历
          for(int i=n-1;i>=0;i--){
            //如果当前栈不为空且栈顶元素小于当前入栈元素，直接进行出栈
            while(!stack.isEmpty()&&stack.peek().val<=temperatures[i]){
                   stack.pop();
            }
            //填充结果
            res[i]=stack.isEmpty()?0:stack.peek().index-i;
            //将当前元素进行入栈
            stack.push(new Pair(temperatures[i],i));
          }
          return res;
        }
        class  Pair{
            private int val;
            private int index;
            public  Pair(int val,int index){
                this.val=val;
                this.index=index;
            }
        }

![9df6eb289bd44433b7622c4f5b3bd660.png][]

[67fd757fef02477fb38b12ce1f4f001c.png]: https://img-blog.csdnimg.cn/67fd757fef02477fb38b12ce1f4f001c.png
[a951ae7103eb4eab9ad43988e688746d.png]: https://img-blog.csdnimg.cn/a951ae7103eb4eab9ad43988e688746d.png
[9df6eb289bd44433b7622c4f5b3bd660.png]: https://img-blog.csdnimg.cn/9df6eb289bd44433b7622c4f5b3bd660.png