739. 每日温度

[Geekhyt]

原题链接

单调栈

一维数组，要寻找任一个元素的右边(左边)第一个比自己大(小)的元素的位置时，第一时间想到用单调栈解题。

1. 初始化一个都为 0 的数组，处理题目要求气温不会升高时，用 0 代替
2. 初始化一个栈，栈中准备存储索引。遍历数组，如果当前元素比栈顶大，则让元素出栈
3. 此时栈顶元素就是当前项的右边的第一个比它大的元素索引，计算出距离存到 res 中
4. 最后返回 res 即可

const dailyTemperatures = (T) => {
  const res = new Array(T.length).fill(0)
  const stack = []
  for (let i = T.length - 1; i >= 0; i--) {
    while (stack.length && T[i] >= T[stack[stack.length - 1]]) {
      stack.pop()
    }
    if (stack.length) {
      res[i] = stack[stack.length - 1] - i
    }
    stack.push(i)
  }
  return res
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)