739. 每日温度

题目描述

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

输入输出

1
2
3
4
5
6
7
8
输入: 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]

大致思路

抽象题意：寻找每一个位置中在它右边最近一个比它大的位置

往后处理使用单调栈(双端队列Deque) 利用Deque保存所有待更新的位置下标 针对temperatures[i]:

  1. 如果比Deque中任意位置温度更低，则不能更新，但将其也加入Deque中。
  2. 如果比Deque中任意位置温度更高，则能够更新，从尾部取出待更新位置来更新答案。

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 暴力解法
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] res = new int[len];
        for(int i = 0; i < len; i++){
            int temp = temperatures[i];
            for(int j = i + 1; j < len; j++){
                if(temperatures[j] > temp){
                    res[i] = j - i;
                    break;
                }
            }
        }
        return res;
    }
}

// 单调栈
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] res = new int[len];
        Deque<Integer> deque = new ArrayDeque<Integer>();
        for(int i = 0; i < len; i++){
            while(!deque.isEmpty() && temperatures[deque.peekLast()] < temperatures[i]){
                int index = deque.pollLast();
                res[index] = i - index;
            }
            deque.addLast(i);
        }
        return res;
    }
}