题目描述
难度：中等
请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/daily-temperatures
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- 单调栈
- 思考了一会儿，有意识往 栈&队列 上套才想出来
- 根据题意我们需要找到下一个更高的气温，然后计算两者相差的天数。我们从前往后依次遍历每天的温度，比如 [73,74,75,71,69,72,76,73]，73 入栈，遍历到 74，发现它比栈顶元素 73 大，那么 73 遇到了第一个比它高的数，73 出栈并记录 ans[栈顶下标] = 当前下标 - 栈顶下标，即 ans[0] = 1-0=1。74 入栈。同理，当遍历到第 5 个数 72 时，栈中元素自底向上为 [ 75,71,69 ], 由于 72 比 69 大，那么 69 遇到了第一个比它高的数，ans[4] = 5-4=1，69出栈，71也遇到了第一个比它高的数，也出栈，ans[3] = 5-3=2。
- 为什么会想到栈呢？因为满足 温度高的数 先进后出，前面的数如果值大进栈，后面只有遇到更大的数，它才会出栈，那些后面比它小的数会后进栈，但是它们更可能会先出栈。
- 单调栈来解决leetcode上的典型问题，它的应用范围不广，主要解决的都是类似于leetcode上的下一个更大元素问题。如果某个元素前面存在比它大 的元素，那么这个元素就被淘汰了，如果比他小，那么可以继续留着和前面的人进行比较，这就有点符合单调栈的思路了，栈底到栈顶单调递减。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int>stk;//维护单调栈 自底向上 从大到小
int n=temperatures.size();
vector<int>ans(n);//记录答案
for(int i=0;i<n;i++){
while(!stk.empty()&&temperatures[stk.top()]<temperatures[i]){//如果栈顶对应温度比当前温度低
int old_day=stk.top();//对于这个 old_day,第一次遇到了比它还高的天气
ans[old_day]=i-old_day;//计算差距天数
stk.pop();
}
stk.push(i);
}
return ans;
}
};
-
官方暴力解法，也很巧妙
-
对于温度列表中的每个元素 temperatures[i]，需要找到最小的下标 j，使得 i < j 且 temperatures[i] < temperatures[j]。
由于温度范围在 [30, 100] 之内，因此可以维护一个数组 next 记录每个温度第一次出现的下标。数组 next 中的元素初始化为无穷大，在遍历温度列表的过程中更新 next 的值。
反向遍历温度列表。对于每个元素 temperatures[i]，在数组 next 中找到从 temperatures[i] + 1 到 100 中每个温度第一次出现的下标，将其中的最小下标记为 warmerIndex，则 warmerIndex 为下一次温度比当天高的下标。如果 warmerIndex 不为无穷大，则 warmerIndex - i 即为下一次温度比当天高的等待天数，最后令 next[temperatures[i]] = i。
为什么上述做法可以保证正确呢？因为遍历温度列表的方向是反向，当遍历到元素 temperatures[i] 时，只有 temperatures[i] 后面的元素被访问过，即对于任意 t，当 next[t] 不为无穷大时，一定存在 j 使得 temperatures[j] == t 且 i < j。又由于遍历到温度列表中的每个元素时都会更新数组 next 中的对应温度的元素值，因此对于任意 t，当 next[t] 不为无穷大时，令 j = next[t]，则 j 是满足 temperatures[j] == t 且 i < j 的最小下标。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n), next(101, INT_MAX);//记录每个温度第一次出现的下标
for (int i = n - 1; i >= 0; --i) {
int warmerIndex = INT_MAX;
for (int t = temperatures[i] + 1; t <= 100; ++t) {//找到从 temperatures[i] + 1 到 100 中每个温度第一次出现的下标
warmerIndex = min(warmerIndex, next[t]);
}
if (warmerIndex != INT_MAX) {//warmerIndex 为下一次温度比当天高的下标
ans[i] = warmerIndex - i;
}
next[temperatures[i]] = i;//记录每个温度第一次出现的下标
}
return ans;
}
};