3-22 739. 每日温度

Date：2022-03-22 07:53:57

标签：

单调栈

单调栈相关题目：

题目：739. 每日温度 ( 中等😕 )

给定一个整数数组 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^2), O(1)
单调栈
维护一个索引的单调栈，每次检测当前元素与栈顶元素的大小，如果超过，则出栈，其天数为当前天数减去栈元素索引。
注意：可以连续出栈
O(n), O(n)

为什么单调栈可以解决这个问题？

涉及到匹配问题
判别是否需要使用单调栈，如果需要找到左边或者右边第一个比当前位置的数大或者小，则可以考虑使用单调栈；单调栈的题目如矩形米面积等等

题解

暴力枚举

function dailyTemperatures(temperatures: number[]): number[] {
  const len = temperatures.length
  const answer: number[] = []

  for (let i = 0; i < len; ++i) {
    for (let j = i + 1; j < len; ++j) {
      if (temperatures[j] > temperatures[i]) {
        answer[i] = j - i

        break
      }
    }

    if (!answer[i]) {
      answer[i] = 0
    }
  }

  return answer
}

单调栈

function dailyTemperatures111(temperatures: number[]): number[] {
  const len = temperatures.length

  if (len <= 0) {
    return []
  }

  // store pos
  const stack: number[] = []
  const answer: number[] = new Array(len).fill(0)

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

      answer[pos] = i - pos
    }

    stack.push(i)
  }

  // while (stack.length > 0) {
  //   const pos = stack.pop()

  //   answer[pos] = 0
  // }

  return answer
}

使用

function main() {
  const temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
  // const temperatures = [30, 40, 50, 60]

  console.log('[]:', dailyTemperatures(temperatures))
  console.log('[]:', dailyTemperatures111(temperatures))
}

main()

export {}

3-22 739. 每日温度

题目：739. 每日温度 ( 中等😕 )​

示例​

分析​

题解​

题目：739. 每日温度 ( 中等😕 )

示例

分析

题解