问题描述

  1. 根据每日气温列T表重新生成一个列表，对应位置分别为想要观测到更高的气温至少需要等待的天数。气温都是[30,100]内的整数。
  2. https://leetcode-cn.com/problems/daily-temperatures/

暴力法

  1. 我想到的暴力法就很low，没有注意到气温范围是[30,100]，因此时间复杂度是O(n*n)
  2. 正确的做法其实有点类似于HashMap的思路，但是由于温度范围是[30,100]所以可以用数组代替HashMap，具体思路如下：
    • 准备一个next数组，以温度为下标，以T的下标为value。
    • 从后往前遍历T，并将对应温度的下标填入next数组。
    • 遍历T[i]到100所有的温度，寻找其中下标最小的index。
    • 时间复杂度O(n*71),空间复杂度O(71)

单调栈

  1. 单调栈的作用：寻找出后面第一个比自己大/小的元素！
  2. 需要注意的点:入栈和出栈不是if-else的关系，入栈是必须的！

KMP

  1. 从后向前遍历，假设$res[i]$记录了位置上$i$上的答案，求$res[i]$时，先判断$T[i+1]$是否大于$T[i]$，如果大于，则$res[i]=1$; 否则，根据$res[i+1]$可以知道后面至少有几个数字是小于$T[i]$的，这些数字不用判断直接跳过即可。从而提高遍历效率。