739. Daily Temperatures

Leetcode link

题目简介

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */

题目给我们一个数字数组 temperatures 代表每天的温度

要求我们返回一个新的数组，数组元素代表要多少天后才会升温

解题思路

这题暴力解法可以用双重循环来做，但也可以借助单调栈来减少一重循环的复杂度

核心思路是，我们在遍历每一个元素的时候，在入栈前判断当前栈顶元素是否比当前元素小，如果是的话需要依序出栈并计算下标的差保存起来

由于这么做栈中元素只会是单调递减的，所以这个栈也叫做单调栈

Javascript

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
    const len = temperatures.length
    const stack = []
    const res = new Array(len).fill(0)

    for (let i = 0; i < len; i++) {
        while (stack.length > 0 && temperatures[stack[stack.length - 1]] < temperatures[i]) {
            const idx = stack.pop()
            res[idx] = i - idx
        }
        stack.push(i)
    }
    return res
};