【hot100】跟着小王一起刷leetcode -- 739. 每日温度
【hot100】跟着小王一起刷leetcode -- 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为0即可；不为0，代表后面可能还有更大的。此时我们要一个个遍历嘛？
显然不是！ 我们直接利用较小值的answer，跳转到较小值坐标+较小值的answer进行判断即可，因为中间的数据都比较小值小了，那怎么可能比当前值大呢。
就这样，循环即可，答案就出来了，并且时间省了很多。
代码
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int index = temperatures.length - 1;
int[] answer = new int[temperatures.length];
answer[temperatures.length - 1] = 0;
for (int i = temperatures.length - 2; i >= 0; i--) {
int after = i + 1;
while (after < temperatures.length) {
// temperatures[after ]比temperatures[i]大，这个时候直接赋值answer数组即可，并且可以停止了，因为我们已经找到了第一个大的。
if (temperatures[after] > temperatures[i]) {
answer[i] = after - i;
break;
}
// temperatures[after]等于temperatures[i]
if (temperatures[after] == temperatures[i]) {
// 经过我们的遍历，i到after之间不存在比temperatures[i]大的值。这是因为如果存在这样的值，我们的上一个循环就停止了。
// 并且after到after+answer[after]之间也不会存在比temperatures[after]大的值，因为answer[after]代表的是after之后第一个比temperatures[after]大的值。
// 综合上述两点，answer[i]=after - i + answer[after];
if (answer[after] != 0)
answer[i] = after - i + answer[after];
else
// 如果answer[after]=0，代表i之后没有比temperatures[i]大的值，因此直接设置answer为0.
answer[i] = 0;
break;
}
// temperatures[after]小于temperatures[i]
// 如果answer[after] 为0的话，都没有比temperatures[after]小的了，那肯定没有比temperatures[i]小的值，所以直接设置answer为0.
if (answer[after] == 0) {
answer[i] = 0;
break;
}
// 这里大家可能看的有点迷，还能这么搞吗，我们来解释下
// 来到这里，说明什么？
// 如果temperatures[after]大于temperatures[i]，第一个判断就截胡了，到不了这。同理temperatures[after]等于temperatures[i]也是如此。
// 同样小于并且answer为0的情况我们也判断了，所以这里只有一种可能
// 也就是temperatures[after]小于temperatures[i]，并且answer还不为0，这个时候再结合咱们在思路的分析，直接这样跳转就可以了。
after=after+answer[after];
}
}
return answer;
}
}总结
时间复杂度还行，就是空间，emmm。。。。。。
腾讯云开发者
