每日温度（LeetCode Medium难度算法题）题解

1083 0 0

作者:vibe

LeetCode 题号739中等难度每日温度

题目描述：

根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

虽说这是一个中等难度的题目，但看完题目后会发现其实要做出来其实不困难，甚至可以说有点简单（单纯的为了AC）

很简单，题目要求就是给一个数组，让你返回一个数组，新数组对应位置表示的是题目给的数组对应位置往后找第一个值比其大的位置距离，如果没有则为0；

直接简单循环遍历就可以通过了。

 1 class Solution {
 2     public int[] dailyTemperatures(int[] T) {
 3         int[] ans = new int[T.length];
 4         for(int i = 0 ; i < T.length-1;i++){
 5             ans[i] = 0 ;
 6             for(int j = i+1;j<T.length;j++){
 7                 if(T[j]>T[i]){
 8                     ans[i] = j-i;
 9                     break;
10                 }
11             }
12         }
13         return ans;
14     }
15 }

这样子就可以ac了，但是效率呢？

先上ac后截图：

223ms- -，吓死个人了。仅仅30%多而已。

在我看来，刷题第一个目标是为了ac，第二个目标是优化。

本人也是个渣渣，也不会优化- -。但是leetcode上有大牛- -。

多说无益直接上大牛代码：

 1 class Solution {
 2    public int[] dailyTemperatures(int[] T) {
 3     int length = T.length;
 4     int[] result = new int[length];
 5 
 6     //从右向左遍历
 7     for (int i = length - 2; i >= 0; i--) {
 8         // j+= result[j]是利用已经有的结果进行跳跃
 9         for (int j = i + 1; j < length; j+= result[j]) {
10             if (T[j] > T[i]) {
11                 result[i] = j - i;
12                 break;
13             } else if (result[j] == 0) { //遇到0表示后面不会有更大的值，那当然当前值就应该也为0
14                 result[i] = 0;
15                 break;
16             }
17         }
18     }
19 
20     return result;
21 }
22 }

看起来好像没有什么变化好像只是菜鸡小老弟我多了个几行- -。

但是我们看看大佬代码ac后的截图

4ms，和菜鸡我的200多ms 比起来我只是个弟中弟。

话不多说来分析一下大佬的精辟思想。

直接看核心代码：

 1 //从右向左遍历
 2     for (int i = length - 2; i >= 0; i--) {
 3         // j+= result[j]是利用已经有的结果进行跳跃
 4         for (int j = i + 1; j < length; j+= result[j]) {
 5             if (T[j] > T[i]) {
 6                 result[i] = j - i;
 7                 break;
 8             } else if (result[j] == 0) { //遇到0表示后面不会有更大的值，那当然当前值就应该也为0
 9                 result[i] = 0;
10                 break;
11             }
12         }
13     }
14 
15 作者：pulsaryu
16 链接：https://leetcode-cn.com/problems/daily-temperatures/solution/jie-ti-si-lu-by-pulsaryu/
17 来源：力扣（LeetCode）
18 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

大佬习惯——代码写注释。

可能有的人看完还不是很懂我们具体再分析一下。

首先，我们肯定要遍历每一个数组元素的值的。那我们优化的点只能是在比较的过程。

回想题目要求，我们是要从当前位置往后面找第一个比该位置值大的位置与他的距离（其实就是下标的差）；

然后把这个距离存进返回的数组对应的位置下标。

我们正常想都是从前往后遍历。但是这题我们每次遍历都得往后找。那我们可以尝试着从后往前即从右往左啦。

再这个基础上，再往后找。

这样子的好处是我们往后找的时候，后方的位置都是已经计算好的。

如果我们的是从前往后遍历，那我们比较永远只能一个位置一个位置都比较找到第一个值大的位置则为止继续找下一个位置。

如果我们已经算好后方的位置呢？

看下大佬的图文：

71的位置对应值2，表明71的后面的的第二个元素就是第一个比71大的位置。

这样子我们就可以跳跃。我们求75位置。往后找的时候，如果后方的比当前位置小，那们我们没有必要j++这样子一个一个看，我们可以直接

根据后方元素的值即result[j]跳跃，我们不用j++；我们可以直接j = j+ result[j];再与75比较如果比75大则返回索引差。

如果后方位置的值比当前位置小并且result[j]==0代表什么呢？就是代表 j 位置后方的都没有j 位置的大。而当前位置又比J位置的大。那当前位置

往后找也找不出一个比其大的位置所以直接result[i] = 0;

每一次计算出当前位置的值后我们就直接break 掉内层循环然后接着遍历前一个元素即可.

其实这种跳跃思想有点像字符串模式匹配用到的KMP算法next数组的思想。

如果不知道KMP是什么的可以点下方连接学习

https://blog.csdn.net/sinat_37537673/article/details/73331135

本人只是个普通二本在读大二的菜鸡，只是个搬运工，不喜勿喷- -。

内容来源于网络如有侵权请私信删除

标签：算法数据结构 LeetCode LeetCode

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

每日温度（LeetCode Medium难度算法题）题解