87 lines
2.9 KiB
JavaScript
87 lines
2.9 KiB
JavaScript
/**
|
||
* @param {number[]} temperatures
|
||
* @return {number[]}
|
||
*/
|
||
const dailyTemperatures = function (temperatures) {
|
||
|
||
};
|
||
|
||
/*
|
||
直接利用单调栈，单调栈中存入的是元素的下标，这样不仅能比较元素，还能通过下标设置结果
|
||
*/
|
||
function f1(temperatures) {
|
||
const res = []; // 收集结果
|
||
const stack = []; // 单调递减栈，寻找右边第一个比栈顶元素大的元素
|
||
|
||
for (let i = 0; i < temperatures.length; i++) {
|
||
// 如果栈为空或者当前元素小于等于栈顶元素，将这个元素的下标压入栈中
|
||
if (!stack.length || temperatures[i] <= temperatures[stack[stack.length - 1]]) {
|
||
stack.push(i);
|
||
} else {
|
||
// 依次比较栈顶元素，直到栈为空，或者当前元素小于等于栈顶元素
|
||
while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
|
||
const cur = stack.pop();
|
||
res[cur] = i - cur;
|
||
}
|
||
// 将当前元素下标压入栈中
|
||
stack.push(i);
|
||
}
|
||
}
|
||
|
||
// 如果栈中还有元素，将其在result中的对应位置设置从0，表示后面没有元素大于当前位置的元素
|
||
for (const i of stack) {
|
||
res[i] = 0;
|
||
}
|
||
|
||
return res;
|
||
}
|
||
|
||
/*
|
||
chatgpt 优化之后的写法，思路没有变，去除了if判断，逻辑如下：
|
||
遍历整个温度，如果单调栈有元素，并且当前元素大于栈顶元素，就一直处理，直到栈中没有元素，或者当前元素小于等于栈顶元素
|
||
然后将当前元素压入栈中
|
||
*/
|
||
|
||
/**
|
||
* 计算每一天需要等待多少天才会有更高温度。
|
||
* 如果后面没有更高的温度，则返回 0。
|
||
*
|
||
* @param {number[]} temperatures - 每天的温度数组
|
||
* @returns {number[]} - 返回一个数组，表示每一天距离下一次更高温度的天数
|
||
*/
|
||
function f2(temperatures) {
|
||
// 初始化结果数组，默认所有值为 0（表示找不到更高温度）
|
||
const res = new Array(temperatures.length).fill(0);
|
||
|
||
// 用来存储下标的单调递减栈（栈顶到栈底的温度依次递减）
|
||
const stack = [];
|
||
|
||
// 遍历温度数组
|
||
for (let i = 0; i < temperatures.length; i++) {
|
||
const currentTemp = temperatures[i];
|
||
|
||
/**
|
||
* 当前温度比栈顶下标对应的温度大，说明当前是“更高温度”的一天，
|
||
* 所以可以开始出栈并记录距离。
|
||
*
|
||
* 注意：每个元素最多被 push 和 pop 各一次，所以总体时间复杂度是 O(n)
|
||
*/
|
||
while (
|
||
stack.length > 0
|
||
&& currentTemp > temperatures[stack[stack.length - 1]]
|
||
) {
|
||
// 栈顶元素下标
|
||
const prevIndex = stack.pop();
|
||
|
||
// 当前天（i）就是之前那天（prevIndex）等待的更高温度的那一天
|
||
res[prevIndex] = i - prevIndex;
|
||
}
|
||
|
||
// 无论如何都要把当前下标压栈，作为之后判断的基准
|
||
stack.push(i);
|
||
}
|
||
|
||
// 栈中剩下的下标所对应的位置已经默认填 0，不需要再处理
|
||
return res;
|
||
}
|