题目

题目来源：力扣（LeetCode）

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 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]

思路分析

对题目的理解
给定列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，为啥输出就是 [1, 1, 4, 2, 1, 1, 0, 0] ？

下面来一个个进行解释。

对于输入 73，它需要 经过一天 才能等到温度的升高，也就是在第二天的时候，温度升高到 74 ，所以对应的结果是 1。

对于输入 74，它需要 经过一天 才能等到温度的升高，也就是在第三天的时候，温度升高到 75 ，所以对应的结果是 1。

对于输入 75，它经过 1 天后发现温度是 71，没有超过它，继续等，一直 等了四天，在第七天才等到温度的升高，温度升高到 76 ，所以对应的结果是 4 。

对于输入 71，它经过 1 天后发现温度是 69，没有超过它，继续等，一直 等了两天，在第六天才等到温度的升高，温度升高到 72 ，所以对应的结果是 2 。

对于输入 69，它 经过一天 后发现温度是 72，已经超过它，所以对应的结果是 1 。

对于输入 72，它 经过一天 后发现温度是 76，已经超过它，所以对应的结果是 1 。

对于输入 76，后续 没有温度 可以超过它，所以对应的结果是 0 。

对于输入 73，后续 没有温度 可以超过它，所以对应的结果是 0 。

解法
维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。

遍历整个温度列表，如果栈不空，且当前数字大于栈顶元素，取出栈顶元素，由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离。

继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来。

以下用一个具体的例子帮助读者理解单调栈。对于温度列表[73,74,75,71,69,72,76,73]，单调栈 stack 的初始状态为空，答案 ans 的初始状态是 [0,0,0,0,0,0,0,0]，按照以下步骤更新单调栈和答案，其中单调栈内的元素都是下标，括号内的数字表示下标在温度列表中对应的温度。

  • 当 i=0 时，单调栈为空，因此将 0 进栈。

    • stack=[0(73)]
    • ans=[0,0,0,0,0,0,0,0]

  • 当 i=1 时，由于 74 大于 73，因此移除栈顶元素 0，赋值 ans[0]:=1-0，将 1 进栈。

    • stack=[1(74)]
    • ans=[1,0,0,0,0,0,0,0]

  • 当 i=2 时，由于 75 大于 74，因此移除栈顶元素 1，赋值 ans[1]:=2-1，将 2 进栈。

    • stack=[2(75)]
    • ans=[1,1,0,0,0,0,0,0]

  • 当 i=3 时，由于 71 小于 75，因此将 3 进栈。

    • stack=[2(75),3(71)]
    • ans=[1,1,0,0,0,0,0,0]

  • 当 i=4 时，由于 69 小于 71，因此将 4 进栈。

    • stack=[2(75),3(71),4(69)]
    • ans=[1,1,0,0,0,0,0,0]

  • 当 i=5 时，由于 72 大于 69 和 71，因此依次移除栈顶元素 4 和 3，赋值 ans[4]:=5-4 和 ans[3]:=5-3，将 5 进栈。

    • stack=[2(75),5(72)]
    • ans=[1,1,0,2,1,0,0,0]

  • 当 i=6 时，由于 76 大于 72 和 75，因此依次移除栈顶元素 5 和 2，赋值 ans[5]:=6-5 和 ans[2]:=6-2，将 6 进栈。

    • stack=[6(76)]
    • ans=[1,1,4,2,1,1,0,0]

  • 当 i=7 时，由于 73 小于 76，因此将 7 进栈。

    • stack=[6(76),7(73)]
    • ans=[1,1,4,2,1,1,0,0]
  1. /**
  2.  * @param {number[]} temperatures
  3.  * @return {number[]}
  4.  */
  5. var dailyTemperatures = function(temperatures) {
  6.   let stack = []
  7.   // 根据题目要求如果之后气温不再升高
  8.   // 该位置用0代替，因此默认值设置为0
  9.   let res = Array(temperatures.length).fill(0)
  10.   for (let i = 0; i < temperatures.length; i++) {
  11.     // 栈不为空且当前索引对应的温度大于栈顶索引对应的温度
  12.     // 说明当前索引对应的温度是比栈顶索引对应的温度更高
  13.     // while循环表示：
  14.     // 当前索引对应的温度比栈中已存索引对应温度高时，则栈顶元素出栈
  15.     while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
  16.       // 栈顶索引出栈后栈的新的大小
  17.       let len = stack.length
  18.       // 前索引对应的温度大于栈顶索引对应的温度
  19.       if (temperatures[i] > temperatures[stack[len - 1]]) {
  20.         // 当前索引与栈顶索引的差值表示的就是需要等待的天数
  21.         res[stack[len - 1]] = i - stack[len - 1]
  22.         // 栈顶索引出栈
  23.         stack.pop()
  24.       }
  25.     }
  26.     // 将当前考察温度的索引入栈，看后面是否有比其高的温度
  27.     stack.push(i)
  28.   }
  29.   return res
  30. };

借鉴： https://leetcode-cn.com/problems/daily-temperatures/solution/leetcode-tu-jie-739mei-ri-wen-du-by-misterbooo/ https://leetcode-cn.com/problems/daily-temperatures/solution/mei-ri-wen-du-by-leetcode-solution/