【hot100】跟着小王一起刷leetcode -- 739. 每日温度

739. 每日温度

题目解读

739. 每日温度

老规矩，咱先看下题目。总结下来就是，你要返回一个answer数组，answer[i]中存储的应该是temperatures数组中比temperatures[i]大的第一个数的下标，如果不存在这样的数，answer[i]置为0即可。

那么咱首先的思路是啥呢

第一个，必然是暴力解法，这不很简单，直接按个遍历temperatures中的数据，然后每遍历一个数的时候，就看看后面第一个比他大的数的下标是啥就行了。

这时候你兴致勃勃写完代码，然后提交上去，结果发现。。。。。。

那怎么让时间降下来呢

咱们考虑考虑，是不是做了无用功

例如哈，咱们在判断的位置为index的answer，也就是计算第一个比**temperatures[index]**的值的位置时，会和后面的值去比较。这使得我们的计算复杂度到了O(n*n)，那有没有可能我在遍历到某个后续值的时候，就知道后面不会再有比他大的值了呢？这样子是不是复杂度就下来了。那该怎么弄呢。

很简单的思路，既然要知道后面的情况，肯定要从后往前遍历嘛？那该怎么做呢？

思路

咱们大概捋一下过程。最后一个下标的answer一定为0，这个没得说，因为都没有值了，肯定不如它大。

那咱们就可以直接从倒数第二个值开始处理了。当前，我们需要判断倒数第二值之后有没有更大的，如果有的话，就设置为更大值下标-当前下标，如果没有就设置为0。这个也很简单，就和倒数第一个比较下就可以了，然后设置就完事了。

到了倒数第三个的时候就不一样了，这时在处理的时候就需要多种讨论了。

接下来咱们来看看

第一种，后续值比当前值大，那没的说，直接设置answer为更大值下标-当前下标即可。
第二种，后续值等于当前值，这时候就有两种情况了。第一种，相等值下标的answer不为0，当前值answer就是相等值下标-当前下标+相等值下标的answer。第二种，相等值下标的answer为0，那当前也直接设置为0就可以了。
第三种，后续值小于当前值。这个时候不要无脑往后遍历，咱们要充分利用现有的信息。判断较小值的answer是为0，为0的话，直接设置当前answer为