zhangdizhangdi

739. 每日温度 🟨

题目

leetcode 中等

题目

给定一个整数数组 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]

题解

单调栈

  • 时间复杂度：O(n)

    其中 n 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。

  • 空间复杂度：O(n)

    其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。

js
function dailyTemperatures(temperatures) {
  const len = temperatures.length
  const ans = new Array(len).fill(0)
  const stack = [] //单调递减栈

  for (let i = 0; i < len; i++) {
    const temp = temperatures[i]

    console.log('♻️ i', i, 'temp', temp)
    console.log('stack', stack.toString(), 'ans', ans.toString())

    // 栈不为空 && 当前温度 > 栈顶索引对应的温度
    while (stack.length > 0 && temp > temperatures[stack[stack.length - 1]]) {
      let prevIndex = stack.pop() // 取出索引
      ans[prevIndex] = i - prevIndex // 计算等待天数
    }

    stack.push(i) // 当前索引入栈

    console.log('stack', stack.toString(), 'ans', ans.toString())
  }

  return ans
}

console.log('🌰', dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
console.log('---------')
console.log('🌰', dailyTemperatures([30, 40, 50, 60]))
console.log('---------')
console.log('🌰', dailyTemperatures([30, 60, 90]))
执行结果
♻️ i 0 temp 73
stack  ans 0,0,0,0,0,0,0,0
stack 0 ans 0,0,0,0,0,0,0,0
♻️ i 1 temp 74
stack 0 ans 0,0,0,0,0,0,0,0
stack 1 ans 1,0,0,0,0,0,0,0
♻️ i 2 temp 75
stack 1 ans 1,0,0,0,0,0,0,0
stack 2 ans 1,1,0,0,0,0,0,0
♻️ i 3 temp 71
stack 2 ans 1,1,0,0,0,0,0,0
stack 2,3 ans 1,1,0,0,0,0,0,0
♻️ i 4 temp 69
stack 2,3 ans 1,1,0,0,0,0,0,0
stack 2,3,4 ans 1,1,0,0,0,0,0,0
♻️ i 5 temp 72
stack 2,3,4 ans 1,1,0,0,0,0,0,0
stack 2,5 ans 1,1,0,2,1,0,0,0
♻️ i 6 temp 76
stack 2,5 ans 1,1,0,2,1,0,0,0
stack 6 ans 1,1,4,2,1,1,0,0
♻️ i 7 temp 73
stack 6 ans 1,1,4,2,1,1,0,0
stack 6,7 ans 1,1,4,2,1,1,0,0
🌰 [
  1, 1, 4, 2,
  1, 1, 0, 0
]
---------
♻️ i 0 temp 30
stack  ans 0,0,0,0
stack 0 ans 0,0,0,0
♻️ i 1 temp 40
stack 0 ans 0,0,0,0
stack 1 ans 1,0,0,0
♻️ i 2 temp 50
stack 1 ans 1,0,0,0
stack 2 ans 1,1,0,0
♻️ i 3 temp 60
stack 2 ans 1,1,0,0
stack 3 ans 1,1,1,0
🌰 [ 1, 1, 1, 0 ]
---------
♻️ i 0 temp 30
stack  ans 0,0,0
stack 0 ans 0,0,0
♻️ i 1 temp 60
stack 0 ans 0,0,0
stack 1 ans 1,0,0
♻️ i 2 temp 90
stack 1 ans 1,0,0
stack 2 ans 1,1,0
🌰 [ 1, 1, 0 ]