每日温度-739

力扣（LeetCode） 链接：https://leetcode.cn/problems/daily-temperatures/

思路

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为 O(n)。

1. 单调栈里存放的元素是什么？

单调栈里只需要存放元素的下标 i 就可以了，如果需要使用对应的元素，直接 T[i]就可以获取。

2. 单调栈里元素是递增呢？ 还是递减呢？

这里我们要使用递增循序（再强调一下是指从栈头到栈底的顺序），因为只有递增的时候，栈里要加入一个元素 i 的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是 i。

即：如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。

使用单调栈主要有三个判断条件。

• 当前遍历的元素 T[i]大于栈顶元素 T[st.top()]的情况

  我们要保持一个递增单调栈（从栈头到栈底），所以将 T[st.top()]弹出，T[i]加入，此时 result 数组可以记录了，result[st.top()] = i- st.top()

• 当前遍历的元素 T[i]等于栈顶元素 T[st.top()]的情况

  将 T[i]加入单调栈 st.push(i)

• 当前遍历的元素 T[i]大于栈顶元素 T[st.top()]的情况

  将 T[i]加入单调栈 st.push(i)

答案

// 版本一
var dailyTemperatures = function (temperatures) {
  const length = temperatures.length
  const res = Array(length).fill(0)
  const stack = []
  for (let i = 0; i < length; i++) {
    if (
      stack.length === 0 ||
      temperatures[i] <= temperatures[stack[stack.length - 1]]
    ) {
      stack.push(i)
    } else {
      while (
        stack.length &&
        temperatures[i] > temperatures[stack[stack.length - 1]]
      ) {
        const resIndex = stack.pop()
        res[resIndex] = i - resIndex
      }
      stack.push(i)
    }
  }
  return res
}

// 版本二
var dailyTemperatures = function (temperatures) {
  const n = temperatures.length
  const res = Array(n).fill(0)
  const stack = [] // 递增栈：用于存储元素右面第一个比他大的元素下标
  for (let i = 0; i < n; i++) {
    while (
      stack.length &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const top = stack.pop()
      res[top] = i - top
    }
    stack.push(i)
  }
  return res
}