单调栈

方法一暴力

对于每个元素而言，都可以向右遍历找到第一个比他的元素返回下标差即可

复杂度分析

时间复杂度O(n^2)
空间复杂度O(n)

方法二单调栈

从左到右创建一个单调递减栈。单调栈的说明可以看这篇文章单调栈

参考代码

  1. class Solution:
  2.     def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
  3.         length = len(temperatures)
  4.         stack,res = [],[0] * length
  5.         for i in range(length):
  6.             while stack and temperatures[stack[-1]] < temperatures[i]:
  7.                 index = stack.pop()
  8.                 res[index] = i - index
  9.             stack.append(i)
  10.         return res

复杂度分析

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