共计 2050 个字符，预计需要花费 6 分钟才能阅读完成。

提示：以后，凡是算法题目的 文章，命名为: 算法题 -(题目名称)-(会使用到的方法)

方法可能不止一个，会根据更新进度 增加题目中的方法部分，这便于在复习的时候 想起方法 而不是直接看答案！

背景：

给一个数组temperatures[]，它的每个元素表示每日的气温，编写一个方法，该方法返回 answer[i] 表示每日的温度的下一个更高的温度 相差多少天

示例 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]

我的思考

这是一个中等难度的题目。我一开始就想到使用双指针，因为我非常倾向于使用双指针来规避 嵌套循环导致的时间复杂度较高的问题。

但我错了，这题无法使用双指针的方法。我使用暴力法解题，会超时！这个题用双指针依旧会有超时的风险。因为每日的温度 不是一个有序 的数据，它不会是递增的、递减的。right 指针很有可能会回头，这导致—— 时间复杂度仍然可能为 O(n²) ==> 超时

这里我粘贴一下 暴力的方法

法一暴力（会超时）

var dailyTemperatures = function(temperatures) {
    // 每日的温度数组
    let len = temperatures.length
    let cur = 0
    let answer = []
    for(let i =0;i<len;i++) {cur = temperatures[i]
        answer[i] = 0
        let day = 0
        for(let j = i+1;j<len;j++) {if(cur >= temperatures[j]) {++day} else {
                ++day
                answer[i] = day
                break
            }
        }
    }
return answer
}

此代码 属于思维简单，但执行复杂了。

法二 单调栈

这个方法，经过提示才得到的。

单调栈：包含单调递增栈、单调递减栈。bing 是这样解释的：保证元素从栈顶到栈底的单调性。单调栈常用于在 $O(n)$ 的时间复杂度内寻找序列中某些元素的相邻元素，如左侧第一个更大 / 更小的元素等。

这正合本题

初始化数据

let answer = new Array(n).fill(0) n 是给的温度参数的长度

let stack = [] // 栈结构 存储温度的天数 索引

for (let i =0; i < n;i++)

我们每次判断 (while) 栈的元素数 > 0 并且 迭代的当前次温度 大于栈顶温度，那么弹出栈顶的元素，并计算 当前的迭代轮数 i 与栈顶的索引之差，就是天数差。然后赋予 answer[top] = i – top 得到了 比这一天温度高的 下一天的天数差

而如果不符合上述的条件，也就是 当前次温度 小于等于 栈顶温度，说明 还没有找到比这一天温度高的下一天，那么将当次 索引压入栈顶

那么，这里的 while 循环，作用是 计算天数差的。

比如一个递减的 温度值会 这样：频繁的将后面的天数 压入栈顶，直到遇见后面的一个温度比栈顶的温度高，那么弹出，并计算天数差，然后 while 接着执行，会进行比较前一天比这一天温度，如果是小于，则弹出前一天，计算差值，这差值 就是天数差。依次类推，直到这一天温度小于，前面某一天，会压入栈顶。

这个方法就很像是这样：一直找找找，，直到遇到了 当天温度(当前迭代次) 比前一天的温度高了，则符合题意了，记录下来天数是 1，那，，，会不会比再前面的天的温度高呢？用 while 不断往前判断，当它比再前一天的温度高，奥！找到了，然后接着再往前找！直到 温度不再大于。

为什么？此为单调栈，保证了从栈顶到栈底的元素一定是从大到小的！

我贴出来代码：

const dailyTemperatures = (temperatures) {

    let stack = []
    let n = temperatures.length
    const answer = new Array(n).fill(0)

    for(let i =0;i<n;i++) {

        // 当栈不为空，且当前温度大于栈顶的温度时 弹出栈顶
        while(stack.length > 0 && temperatures[i] > temperatures[stack[stack.length -1]]) {const top = stack.pop()
            answer[top] = i - top
        }
        // 当前温度小于栈顶温度
        stack.push(i)
    }


    // 这题使用双指针 无法通过，原因是 数据是无序的，而不是递减的，我们无法保证 j 不会回头  这可能导致时间复杂度仍然为 O(n)

    return answer
}

为什么这个方法 更好？

• 栈的单调性：栈中始终保持“索引对应的温度递减”，因此当遇到更高温度时，栈顶元素的“下一个更高温度”一定是当前 i（因为栈中元素是按顺序入栈的，中间没有更高温度）。
• 每个元素仅处理一次：每个索引会被压入栈一次，弹出一次，总操作次数是 O (n)，彻底避免了二层循环的冗余遍历。

总结：

此题目，我学会了单调栈的使用，这是一个新的技巧，需要积累

它主要处理：在 $O(n)$ 的时间复杂度内寻找序列中某些元素的相邻元素，如左侧第一个更大 / 更小的元素等。