题目描述

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

示例 1:

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

具体见题目描述。

算法思路

这道题我写的自认为是$O(n)$的复杂度，但仔细分析后其实应该接近$O(n^2)$算法很简单：直接从当前温度开始找下一个温度高的天数即可，代码如下：

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
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans;
        if (temperatures.size() <= 1) {
            ans.push_back(0);
            return ans;
        }
        int i = 0, j = 1;
        while(i < temperatures.size() - 1) {
            if (temperatures[j] > temperatures[i]) {
                ans.push_back(j - i);
                i++;
                j = i + 1;
                continue;
            }
            else {
                j++;
                if (j < temperatures.size()) {
                    continue;
                }
                else {
                    ans.push_back(0);
                    i++;
                    j = i + 1;
                    continue;
                }
            }
        }
        ans.push_back(0);
        return ans;
    }
};

​ 只有一层循环，但是我们操作两个指针i,j，所以最后是 $n^2$复杂度，毫不意外超时了(测试样例通过46/48)，这要是蓝桥杯那种OJ说不定就算了。

算法优化

​ 我考虑过算法优化，进行简单的剪枝，但是天色有点晚了，懒得动，大体思路是，用一个临时变量去记录此次寻找过程中的最大温度值 tmp_max，当进行下一个位置的查找时，如果temperature[i+1] < tmp_max，那说明i, j 之间必有一值k满足 $temperature[k] > temperature[i], i < k <= j$ ，此时将j设置为i+1即可。否则我们不需要将j移回来，直接j设置为j+1开始遍历。或许可以过最后两个测试样例？但是我觉得提升不大，就没有尝试

借鉴思路

方法1-单调栈

​ 单调栈这个思路真的很高效，我也感觉很容易想出来，但是真的就是差了一点，最后看的是官方题解。主要利用 递减栈 ：栈里面只有递减元素。

算法流程如下：

  1. 第一个元素先入栈。从第二个元素开始执行下列操作：
  2. 如果当前数字大于栈顶，那么就直接取出栈顶，ans[栈顶元素索引] = 当前元索引 - 栈顶元素索引 。
  3. 如果当前数字小于栈顶，那么将其入栈，作为新的栈顶，继续看新的元素，转2。

​ 非常好理解，关键就是需要把元素的索引入栈，此时需要理解他们的数值对应关系，否则不好计算天数。复杂度为 O(n) 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0);
        stack<int> st;
        for (int i = 0; i < temperatures.size(); ++i) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                auto t = st.top(); st.pop();
                res[t] = i - t;
            }
            st.push(i);
        }
        return res;
    }
};

方法2-线性探测+倒序遍历

​ 这道题目的标签是 单调栈 ，但是我看到一个比较容易理解的思路，使用了 线性探测 + 倒序遍历，其实我认为 倒序遍历 是这个题目的核心，因为整个题目就是需要向后检测，如果后面的子问题解决了，前面的问题解决起来比较轻松；线性探测 在这个题目里也比较聪明，先看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int len = temperatures.size();
        vector<int> ans(len);
        for (int i = len - 2; i >= 0; i--) {
            int compare = i + 1;
            while (temperatures[i] >= temperatures[compare]) {
                if (ans[compare] == 0) {
                    break;
                }
                else {
                    compare += ans[compare];
                }
            }
            if (temperatures[i] < temperatures[compare]) {
                ans[i] = compare - i;
            }
        }
        return ans;
    }
};

​ 我们记结果为 ans ，比较数的索引为 compare ，数组长度为 n ， 算法流程如下：

  1. 从倒数第二个数开始，先看其后面一个数，如果最后一个数大于倒数第二个数，那么很显然ans[n - 2] = 1，否则 ans[n - 2] = 0 。
  2. 然后再去看第i个，先比较 temperature[i]和temperature[compare]，如果 $temperature[i] < tempareture[compare]$ ， 那么 ans[i] = compare - i ，否则我们需要找到比 tempareture[compare]大的那个温度，很显然，这个温度是 ans[compare]，然后以这个 ans[compare]为比较值，转2继续比较。
  3. 最后肯定会因为while循环不满足，或者 res[compare] != 0 跳出这个循环，此时再比较 temperature[i]和temperature[compare]的结果确定这个ans[i]是compare-i还是0。