Leetcode（739）——每日温度

题目

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

示例 1：

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

示例 2：

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3：

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

题解

方法一：暴力解法

思路

????两层 for 循环，把至少需要等待的天数计算出来。

代码实现

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> answer(temperatures.size(), 0);
        for (int i = 0; i < temperatures.size() - 1; i++) {
            for (int j =  i + 1; j < temperatures.size(); j++) {
                if (temperatures[j] > temperatures[i]) {
                    answer[i] = j - i;
                    break;
                }
            }
        }
        return answer;
    }
};

复杂度分析

时间复杂度： $O(N^2)$ ，数组 temperatures 长度为 $N$ ，算法使用两层 for 循环遍历了 $N^2$ 次数组 temperatures。远比后两个方法要更加耗时。
空间复杂度： $O (N)$ ，保存结果需要长度为 $N$ 的数组

方法二：单调栈

思路

????我们可以将问题转换为另一种问法：查找数组中比每个值大的第一个值，并求它们的下标之差，类似之前的 leetcode（20）——有效的括号。
????我们可以发现以下规律：

若找到比值 A 大的第一个值 B，则在 A 和 B 之间的全部值都比 A 要小，且序列 [A,B) 是降序排序，即序列中的数都比前一个数小或者相等；
类似 leetcode（20）——有效的括号，若以 A 和 B 为一对，此时我们发现序列 [A,B) 的子序列也是类似于它的降序排序。所以问题的解实际上是从最小子序列一步步去除，直到最大子序列被去除为止，比如 [71,65,61,76] ，先去除 (61,76)，再去除 (65,76)。
此时我们又发现，与括号不同，有时候几个值之可能与同一值是一对的。比如 [71,65,61,76] ，(61,76)和(65,76)。

算法实现：

遍历整个数组，且用栈保存值对应的下标，并进行下面判断：
如果栈不空，且新值大于栈顶值对应的值，修改存储结果的数组中对应下标的值为二者的距离（ $新值对应的下标 ? 栈顶值$ ），再取出栈顶值。
重复第2步，直到不满足条件为止。然后将新值入栈，这样就可以一直保持单调栈，且每个数字和第一个大于它的数的距离也可以算出来。

代码实现

初始版本：（因为嵌套了3层循环，所以时间复杂度很高）

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> tmp;     // 临时栈
        vector<int> answer; // 记录结果
        int n;

        // 每一次tmp入栈，都给 answer 添加0到数组末尾，若有更高温度（即对应旧值出栈）则修改其值
        for(auto &val: temperatures){
            if(tmp.empty()){    // 刚开始时，tmp为空栈，对空栈执行 top 操作是错误的
                tmp.push(val);
                answer.push_back(0);
            }else{
                while(!tmp.empty() && tmp.top() < val){  // 即新值是否大于栈的当前最小值
                    tmp.pop();
                    // 从与当前最大值在栈中位置最近的值开始，修改其在 answer 中对应的值，因为之前没有修改所以一定是0
                    n = answer.size()-1;
                    while(0 <= n){
                        if(answer[n] == 0){
                            answer[n] = answer.size()-n;
                            break;
                        }else n--;
                    }
                }
                tmp.push(val);
                answer.push_back(0);
            }
        }
        return answer;
    }
};

优化版本：（存储的不再是数组 temperatures 的值，而是其值对应的下标，这样做可以方便计算差值，又因为同时取下标对应值是常数级的操作，所以大幅度减少了时间复杂度。最后省略了上一个版本的最内层循环）

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> tmp;     // 临时栈
        int l = temperatures.size();
        vector<int> answer(l, 0); // 记录结果
        int n;

        if(l == 1) return answer;    // 刚开始时，tmp为空栈，对空栈执行 top 操作是错误的
        for(int n = 0; n < l; n++){
            while(!tmp.empty() && temperatures[tmp.top()] < temperatures[n]){  // 即新值是否大于栈的当前最小值
                // 从与当前最大值在栈中位置最近的值开始，修改其在 answer 中对应的值
                answer[tmp.top()] = n-tmp.top();
                tmp.pop();
            }
            tmp.push(n);    // 存储下标
        }
        return answer;
    }
};

复杂度分析

优化版本的：
时间复杂度： $O (N)$ ，其中 $N$ 是数组 temperatures 的长度，算法实际上相当于遍历了长度为 $2 N$ 的数组，再加上常数级别的栈操作
空间复杂度： $O (N)$ ，其中 $N$ 是数组 temperatures 的长度，为栈和结果数组的空间之和

方法三：不使用栈，使用动态规划（DP）

思路

????根据题意，从最后一天推到第一天，这样会简单很多。因为最后一天显然不会再有升高的可能，结果直接为0。再看倒数第二天的温度，如果比倒数第一天低，那么答案显然为1，如果比倒数第一天高，又因为倒数第一天对应的结果为0，即表示之后不会再升高，所以倒数第二天的结果也应该为0。
????自此我们容易观察出规律：要求出第 i 天对应的结果，只需要知道第 i+1 天对应的结果即可算出——（这很明显符合动态规划适用问题的特征：具有最优子结构和重叠子问题）：

状态转换方程——即如何求 temperatures[i] 的值：
比较 temperatures[i] 和 temperatures[i+1] 的大小：

若 temperatures[i] < temperatures[i+1]，那么 answer[i]=1；
若 temperatures[i] > temperatures[i+1]，那么判断 answer[i+1] 的值：
- 若 answer[i+1] 为0，那么 answer[i]=0
- 若 answer[i+1] 不为0，那就比较 temperatures[i] 和 temperatures[i+1+answer[i+1]]（也就是将第 i 天的温度与比第 i+1 天大的那天的温度进行比较），然后根据比较的结果重复执行前面的步骤，直到求出 answer[i] 的值。

可以看出，设问题为求出第 i 天对应的结果（即求出 answer[i] 的值），则其子问题为比较 temperatures[i] 和 temperatures[i+1] 的大小和求出第 i+1 天对应的结果，所以

最优子结构：这里的“最优”指比第 i 天的温度更高的那些天中距离最近的。
重叠子问题：要求出第 i 天对应的结果，则必须先求出第 i+1 天对应的结果，甚至有时还要求出比第 i+1 天的那天温度更高的那一天。

代码实现

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> answer(temperatures.size(), 0);
        int l = answer.size();
        for (int i = l - 2; i >= 0; i--){	// 因为最后一天一定为0，所以从倒数第二个数开始遍历
            for (int j = i + 1; j < l; j += answer[j]) {
                if (temperatures[i] < temperatures[j]) {
                    answer[i] = j - i;
                    break;
                } else if (answer[j] == 0) {
                    answer[i] = 0;
                    break;
                }
            }
        }
        return answer;
    }
};

复杂度分析

时间复杂度： $O (N)$ ，其中 $N$ 是数组 temperatures 的长度。虽然采用了嵌套 for 循环，但时间复杂度不会是 $O(N^2)$ ，因为内循环是跳跃的，实际上与方法二的单调栈的内循环次数一样。
空间复杂度： $O (N)$ ，实际上比方法二要少很多空间，因为没有使用栈