题目
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
我的代码（Python）
version I
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function(temperatures) {
let result = new Array(temperatures.length).fill(-1);
let i = 0;
while (i < temperatures.length) {
let start = i;
let currMin = temperatures[i];
let calSet = new Set();
while (i < temperatures.length) {
i++;
if (temperatures[i] > temperatures[start]) {
break;
} else if (temperatures[i] > currMin) {
for (let j = i - 1; j > start; j--) {
if (calSet.has(j)) {
continue;
} else if (temperatures[j] < temperatures[i]) {
result[j] = i - j;
calSet.add(j);
} else {
break;
}
}
currMin = temperatures[i];
} else {
currMin = temperatures[i];
}
}
for (let j = start; j < i; j++) {
if (calSet.has(j)) {
continue;
} else {
if (i < temperatures.length) {
result[j] = i - j;
} else {
result[j] = 0;
}
}
}
}
return result;
};version II
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function(temperatures) {
let result = new Array(temperatures.length).fill(0);
let i = 1;
let calStack = [0];
while (i < temperatures.length) {
if (temperatures[i] > temperatures[calStack[calStack.length - 1]]) {
while (calStack.length > 0 && temperatures[calStack[calStack.length - 1]] < temperatures[i]) {
result[calStack[calStack.length - 1]] = i - calStack[calStack.length - 1];
calStack.pop();
}
}
calStack.push(i);
i++;
}
return result;
};点评
首先考虑到的是从前往后找，如果找到的是相等或者递减则继续，否则回头比较并且赋值。不过这样会超时，因为每遇到一个较大的就得回头找一次，即使每个位置有判断，遍历次数仍然非常多。
后来用了SET记录计算过的位置，也就是Version I，通过了，但是时间空间效率都很差。
再进一步想到，可以用栈来处理，遇到大的就从栈顶弹出并且赋值，一直到栈空或者比当前这个值大，则把当前索引入栈并且继续，也就是Version II。效率中等，可能还有细节可以优化。
和官方的解法2一样。
解法1虽然效率未必高，但是思路很有趣，跳出了直接计算的限制。在元素本身范围受限的情况下，还是很有用的，有很多题目会用到这个思路，比如计算两数和等。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog