注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(65)-每天的温度[算法]  

2018-01-11 03:47:53|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
问题:定一个存储每天温度的整数数组,如何生成另外一个数组其中每个数字表示我们还需要等待几天才出现更高的温度?如果以后没有更高温度的日子,则用0表示。

例如:输入表示温度的数组为[73, 74, 75, 71, 69, 72, 76, 73],则输出的数组为[1, 1, 4, 2, 1, 1, 0, 0]。

分析:这是LeetCode第739题。


我们不难想出这个题目最直观的解法。当我们针对每一天的温度,扫描位于它右边的数组看要过几个数字才出现更大的数字。对于长度为n的数组中的每个数字,我们可能拿它和后面的每个数字做比较,所以时间复杂度是O(n^2)。

 

下面我们再寻找只需要扫描一次输入数组的算法。如果某一天的温度比它后面一天的温度低,比较好办,只需要等一天就有更高的温度了。如果某一天的温度比它后面一天的温度高,我们需要把保存到某一种数据容器里,等出现更高温度的时候我们比较两天在数组中下标的距离就知道需要等待几天了。

 

我们可以使用一个栈保存在在它之后暂时还没有出现更高温度的日子的下标。当扫描到一个新的温度时,和栈里的温度(也就是之前的温度)比较,如果当前温度比位于栈顶的温度要高,表示我们找到了一个位于栈顶那一天温度更高的温度,我们可以计算那一天需要等待几天才能有更高的温度了。接下来把位于栈顶的那一天从栈里弹出,继续比较位于栈顶的温度和当前扫描的温度。直到把所有比当前温度低的全部从栈里弹出之后,把当前温度压入到栈里。

 

这种思路的Java实现代码如下:

程序员面试题精选100题(65)-每天的温度[算法] - 何海涛 - 微软、Google等面试题
 

 

在上述代码中,实际上压入栈里的是每一天温度对应的下标,因为基于下表既然方便得到对应的温度,又能很方便地根据下表的差值求出还需要等待的天数。

 

上述代码中,由于每个温度最多只需要进栈一次,因此时间复杂度是O(n)。同时由于需要一个栈,因此空间复杂度也是O(n)。

本文转载自微信公众号“青云算法”。扫描下面的二维码,关注“青云算法”微信公众号,学习更多高频算法面试题的解法。

程序员面试题精选100题(65)-每天的温度[算法] - 何海涛 - 微软、Google等面试题

  评论这张
 
阅读(307)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018