在老家过完粽子节,回到工作地又可以一脸开(无)心(奈)地刷leetcode了。今天的题目是每日温度,给定一个温度数组,求解的目标是算出某一天需要等待几天才能超过该天的温度。
每日温度
请根据每日气温列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用0
来代替。
例如,给定一个列表temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
,你的输出应该是[1, 1, 4, 2, 1, 1, 0, 0]
。
提示:气温列表长度的范围是[1, 30000]
。每个气温的值的均为华氏度,都是在[30, 100]
范围内的整数。
两层循环判断
整体思路是,利用两层for
循环,判断每个温度之后是否有更高的温度。要注意,第一层for
循环到最后一个元素时,是不会进入第二层for
循环的。此时直接通过push
方法把0
塞入数组。
1 | /** |
执行结果是:
内存占用45.8M,超过100%用户?
执行时间924ms,竟然只超过了20.19%的用户。
考虑边界
考虑温度的边界,如果当前温度是100,那肯定就不用进第二层循环了。
1 | var dailyTemperatures = function(T) { |
new Array & fill
提交解法后,我看了一下第一名的解法,还是学到了一点东西。
主要有两个地方不太一样:
- 一个是使用
new Array
预先声明好数组空间,在大数组时性能表现更佳; - 第二个是使用了
Array.prototype.fill
预填充0
,所以也不需要判断是否需要进第二层循环。
1 | var dailyTemperatures = function(T) { |
特意对比了一下fill
和push
的执行时间,原来fill
的性能挺好的。
1 | console.time('fill计时'); |
如果给数组初始化1000个值为0的元素呢?不得不说,数据量越大,fill
性能越好。
1 | // fill计时: 0.01220703125ms |
再看了看fill
的兼容性,我只想说,在LeetCode中别怕,给我用最新的特性,IE不兼容的fill
都可以用上。
最后再把第一名的代码放上去提交一遍,尼玛,啪啪打脸。
同样的代码人家执行耗时132ms
,我这里提交就是执行耗时872ms
。我只想问,LeetCode执行用时是怎么算出来的?
不过有一说一,第一名的解法确实性能更好,写法也很优雅,值得学习。