Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给一列温度值,问对于第i天,要等多少天,温度才会大于当前第i天的值

栈操作,从序列最后一位开始处理,如果遇到更高的温度就不断pop栈顶,栈中只需要记录保留下来的日期,可以不用记录那一日的温度值(但很奇怪的是我同时记录温度值反而Memory用得少。。)

以下为两个版本的代码
Version1:不记录温度值

 1 #739
 2 #Runtime: 3649 ms
 3 #Memory Usage: 27.2 MB
 4 
 5 class Solution(object):
 6     def dailyTemperatures(self, temperatures):
 7         """
 8         :type temperatures: List[int]
 9         :rtype: List[int]
10         """
11         stk = []
12         stk.append([1])
13         ans = []
14         ans.append(0)
15         for i in range(len(temperatures)-2, -1, -1):
16             while len(stk) > 0 and temperatures[i] >= temperatures[len(temperatures) - stk[-1][0]]:
17                 stk.pop(-1)
18             if len(stk) > 0:
19                 ans.append((len(temperatures) - i) - stk[-1][0])
20             else:
21                 ans.append(0)
22             stk.append([len(temperatures) - i])
23         ans.reverse()
24         return ans
25                 


Version2:记录温度值

 1 #739
 2 #Runtime: 3789 ms
 3 #Memory Usage: 26.9 MB
 4 
 5 class Solution(object):
 6     def dailyTemperatures(self, temperatures):
 7         """
 8         :type temperatures: List[int]
 9         :rtype: List[int]
10         """
11         stk = []
12         stk.append([temperatures[-1], 1])
13         ans = []
14         ans.append(0)
15         for i in range(len(temperatures)-2, -1, -1):
16             while len(stk) > 0 and temperatures[i] >= stk[-1][0]:
17                 stk.pop(-1)
18             if len(stk) > 0:
19                 ans.append((len(temperatures) - i) - stk[-1][1])
20             else:
21                 ans.append(0)
22             stk.append([temperatures[i], len(temperatures) - i])
23         ans.reverse()
24         return ans

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理