力扣LeetCode 739题：每日温度（单调栈）

布满荆棘的人生 2023-02-17 05:28 31阅读 0赞

题目：

> 根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。  
>   
> 例如，给定一个列表 temperatures = \[73, 74, 75, 71, 69, 72, 76, 73\]，  
> 你的输出应该是 \[1, 1, 4, 2, 1, 1, 0, 0\]。  
> 提示：气温 列表长度的范围是 \[1, 30000\]。每个气温的值的均为华氏度，都是在 \[30, 100\] 范围内的整数。

**分析：题目的意思应该叫做“对于数组的每一个元素，寻找下一个比他大的元素与他的距离”。例如对于 73 下标为 0 ，下一个比他大的元素为 74 下标为 1 ，那么就填入 1-0=1 。以此类推。**

### 一、暴力 ###

直接能够想到的方法就是暴力遍历，对于每一个元素向后遍历：

class Solution {
        
        public int[] dailyTemperatures(int[] T) {
        
            int size=T.length;
            int[] ans=new int[size];
            for(int i=0;i<size;i++){
        
                int j=i;
                while(j<size && T[j]<=T[i]){
        
                    j++;
                }
                //跳出之后没超范围，说明是合法找到
                if(j<size){
        
                    ans[i]=j-i;
                }else{
        
                    ans[i]=0;//否则是溢出而结束
                }
            }
            return ans;
        }
    }

时间空间都比较差，最差的情况下，试想，如果温度全部是降序，那么对于每一个元素，都会遍历一整遍到数组末尾，那么时间复杂度是 O(n2)。

### 二、单调栈 ###

由于之前做过最大矩形面积的题目，用过单调栈这个东西，因此想到了他。

回想一下在示例中：\[73, 74, **75, 71, 69, 72, 76,** 73\]

上一种方法在 75~76 这段，做了很多重复的工作。

实际上当 75 找到比他大的答案是 76 的时候，这两者中间几个元素的答案范围相应缩小了，但是暴力的做法却仍然在盲目进行。所以我们想到用单调栈。

维护一个**单调递减**的栈，但是不是维护数组的值，而是下标，每次判断用下标到数组里去取值。

知道定义之后，我们选择先来模拟这种方法的步骤，更加方便的计算结果：

*  i=0，入栈： 0
 *  i=1，不满足递减，出栈：0 ，1-0=0，得到答案这是 ans\[0\] ；
 *  i=1，入栈： 1
 *  i=2，不满足递减，出栈：1，2-1=1，得到答案这是 ans\[1\]；
 *  i=2，入栈：2
 *  i=3，入栈：2 3
 *  i=4，入栈：2 3 4
 *  i=5，不满足递减，出栈：4，5-4=1，得到答案这是 ans\[4\]；
 *  i=5，不满足递减，出栈：3，5-3=2，得到答案这是ans\[3\]；
 *  i=5，入栈：2 5
 *  i=6，不满足递减，出栈：5，6-5=1，得到答案这是 ans\[5\]；
 *  i=6，不满足递减，出栈：2，6-2=4，得到答案这是 ans\[2\]；
 *  i=6，入栈：6
 *  i=7，入栈：6 7
 *  数组已经遍历结束，剩下的说明都是递减的，那么都出栈并且记为0，ans\[6\]=0,ans\[7\]=0

可以看到如果使用单调栈，上面会有两个连续出栈的过程，这就是相比暴力法改进了很多的地方。

确定了处理流程之后，我们还要考虑实现的一些细节：

1.  递减的条件是 >= 还是 > ? 是 >=；（试想 \[ 1 ,1 ,2 \]对于第一个 1 的答案应该是 2-0=2，所以第二个 1 也要入栈）
2.  出栈的条件是 < ，什么情况入栈呢？看到上面的例子里在啊 i =5 的时候是有连续出栈的，因此只要满足 < 需要连续出栈，while 循环来封装。

class Solution {
        
        public int[] dailyTemperatures(int[] T) {
        
            int size=T.length;
            int[] ans=new int[size];
    
            Deque<Integer> stack=new ArrayDeque<>();
    
            int i=0;
            while(i<size){
        
                int temp=T[i];
                //出栈条件是不满足递减，并且可能一直不满足，是 while 而不是 if
                while(!stack.isEmpty() && T[stack.peek()]<temp){
        
                    int j=stack.pop();//出栈
                    ans[j]=i-j;//写答案
                }
                stack.push(i);//如果没有异常就入栈
                i++;
            }
            return ans;
        }
    }

### 三、暴力法改进 ###

直接使用暴力法能否再进一步改进呢？

如果倒过来看这个问题，ans 仍然记为结果数组。

以题目的示例来看这个过程：\[73, 74, 75, 71, 69, 72, 76, 73\]

*  i = 7，显然ans\[ 7 \]=0;
 *  i = 6，和后一个比较，显然 ans\[ 6 \]=0；
 *  i = 5，和后一个比较，ans\[ 5 \]=1；
 *  i = 4，和后一个比较，ans\[ 4 \]=1；
 *  i = 3，和后一个比较，71>69，而 **ans\[ 4 \] !=0** ，**说明有比 69 大的**，我们只需要看比 69 大的那个数是不是也大于 71 ，找到 T\[ 3+1+ans\[ 3+1 \] \]=76，大于71，所以我们找到了答案就是，3+1+ans\[ 3+1 \]\- 3=2.

到这一步的时候我们发现了两个问题：

1.  这样利用后面结果的“跳跃查找”方式，比暴力法合理了很多；
2.  如果一次跳跃之后仍然得不到结果，比如 ans\[4\] !=0，  
    但是，对应的 T\[ 4+ans\[4\] \] 也并不 > 当前的 T\[i\] ，那么如果对应的  
    ans\[ 5 \]!=0，就不能停止，而要继续跳跃。

这种做法应该是动态规划，状态转移方程就是：

*  若 T\[i\] < T\[i+1\]，那么 ans\[i\]=1；
 *  若 T\[i\] > T\[i+1\]
    
     *  ans\[i+1\]=0，那么 ans\[i\] = 0;
     *  ans\[i+1\]!=0，那么比较 T\[i\] 和 T\[ i+1 + res\[i+1\] \] ，这两个作为新的 T\[i\] 和 T\[i+1\]

从第二种情况看，**“前一个状态”并不能完全解决当前状态的问题，有可能会继续追溯，个人认为这种方法更像是跳跃的递归**而不是动态规划。

但是这道题目，可能对栈的使用和频繁增删操作，时间大于数组的直接访问，用这种递归方法时间远远比单调栈少？（又或者只是力扣日常出bug）  
最终代码如下：

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