❓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<=10^5$
• 30 <= temperatures[i] <= 100

💡思路：

法一：暴力

大多数人看到该题目的第一思路可能就是暴力求解，即对每个数都往后一个一个查找，直到找到比当前数大的为止；

我们可以再多想一步，能否利用前面的搜索信息，从而降低搜索量，这时我们就可以从后往前遍历该数组：

• 除了最后一个元素外，对每元素都先和紧接该元素之后的比较，如果后一个元素大于当前元素，我们就找到了下一个最高温度，结果保存为1（这也是我们最希望处理的）；
• 如果紧接该元素i之后的元素小于等于当前元素，那么我们就查找紧接该元素之后的元素的下一个更高温度（因为我们是从后往前遍历，所以后面的结果我们都已经得到。）直到找到比i更高温度，或者找到最后都没有，则结果为0。

法二：单调栈

观察发现，我们要找的结果，可以由数组的索引获得，如果这一天的温度比前一天的温度高，前一天的结果就等于这一天的数组索引减去前一天的数组索引，结果为1：

• 所以我们可以利用栈，保存数组索引，如果当前索引的温度，高于栈顶索引对应的温度，则栈顶索引处的结果ans[indexs.top()]就等于当前索引curIndex 减去 栈顶索引值indexs.top()，然后出栈，再和栈顶比较，直到不高于栈顶索引对应的温度；
• 如果不高于栈顶索引对应的温度，则当前索引curIndex 入栈；

🍁代码：(Java、C++)

法一：暴力
Java

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] ans = new int[n];ans[n - 1] = 0;for (int i = n - 2; i >= 0; i--) {if (temperatures[i] < temperatures[i + 1]) {ans[i] = 1;}else {int j = i + 1;ans[i] = 1 + ans[j];j += ans[j];while (j < n) {if (temperatures[i] < temperatures[j]) {break;}else if (temperatures[i] >= temperatures[j] && ans[j] != 0) {ans[i] += ans[j];j += ans[j];}else{ans[i] = 0;break;}}}}return ans;}
}

C++

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> ans(n);ans[n - 1] = 0;for (int i = n - 2; i >= 0; i--) {if (temperatures[i] < temperatures[i + 1]) {ans[i] = 1;}else {int j = i + 1;ans[i] = 1 + ans[j];j += ans[j];while (j < n) {if (temperatures[i] < temperatures[j]) {break;}else if (temperatures[i] >= temperatures[j] && ans[j] != 0) {ans[i] += ans[j];j += ans[j];}else{ans[i] = 0;break;}}}}return ans;}
};

法二：单调栈
Java

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] dist = new int[n];Stack<Integer> indexs = new Stack<>();for (int curIndex = 0; curIndex < n; curIndex++) {while (!indexs.isEmpty() && temperatures[curIndex] > temperatures[indexs.peek()]) {int preIndex = indexs.pop();dist[preIndex] = curIndex - preIndex;}indexs.add(curIndex);}return dist;}
}

C++

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> ans(n);stack<int> indexs;for (int curIndex = 0; curIndex < n; curIndex++) {while (!indexs.empty() && temperatures[curIndex] > temperatures[indexs.top()]) {ans[indexs.top()] = curIndex - indexs.top();indexs.pop();}indexs.push(curIndex);}return ans;}
};

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：$O(n)$，其中 n 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。暴力法小于$O(n^2)$。
• 空间复杂度：$O(n)$，其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！

注： 如有不足，欢迎指正！