基本信息

  • 题号：739
  • 题厂：脸书
  • 难度系数：中


已知一个数列，数据代表每日温度。返回一个数组，内容为：需要等待气温升高的天数

例如：temperatures = [73,74,75,71,69,72,76,73]，
返回 [1,1,4,2,1,1,0,0]

第一天气温 73， 第二天气温 74，从第一天到第二天一共等待了 1 天就迎来升温；1 号位填 1
第二天气温 74， 第三天气温 75，从第二天到第三天一共等待了 1 天也迎来升温，所以 2 号位填 1
……以此类推……

……最后一天因为不知下一天的天气，所以返回 0 🐮


解题思路

不知道什么是 「monotonic stack」的小白是不可能做出这道题的

「monotonic stack」是 「stack」的一种升级版。在「stack」先进后出的原理下，「monotonic stack」只添加递减元素，一旦发现超标，在 pop 出来🙈

本题只要熟悉并理解啥是 「monisonic stack」就能解题了😵

  • 创建一个 stack，气温不超标就往 stack 添加当前气温的 index；
  • 超标（升温），就 pop 出来，计算间隔天数，从而解答……
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # 初始一个长度为天气数组，内容全为 0 的数组，用于返回
        res = [0] * len(temperatures)
        # 创建 stack pair: [temp, index]
        stack = []
        
        # 遍历「天气」数组，一旦当前气温高于 stack 最后一天的气温，就从 「stack」 pop，并计算相差天数，存入 res
        for i, t in enumerate(temperatures):
            while stack and stack[-1][0] < t:
                tem, index = stack.pop()
                res[index] = i - index
            
            # 如果不是升温情况，就要把当前气温数据存入 stack    
            stack.append([t, i])
          
        return res


Constraints

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

遇上此题，可以向考官讨论数组最小长度，最大长度。于是本题无需考虑数组为空情况……


Big O

  • Time：O（n）
  • Space：因为 stack 介入 O（n）


测试

  • 递增序列
  • 递减序列
  • 递增递减混合序列
  • 序列长度为 1 时的 edge case
  • ……


总结

  • 就算法难度和成型代码复杂度来说，中规中矩中档题；
  • 然而 「monotonic stack」属于较高难度算法，略难略偏；本题可作为小白从基础 「stack」向中高级「monotonic stack」进阶定期复习🥲。