Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
输入一列股票价格,对于每个输入price,计算从当前日期往前算,一共有多少天的价格是小于等于当前日的

栈操作,每次有新一日的股票价格输入,就不断与栈顶元素比较,不断pop掉小于等于当日价格的栈顶元素,同时记录每一个价格对应的日期

 1 #901
 2 #Runtime: 886 ms
 3 #Memory Usage: 18.8 MB
 4 
 5 class StockSpanner(object):
 6 
 7     def __init__(self):
 8         self.stack_data = [[10001, 0]]
 9 
10     def next(self, price):
11         """
12         :type price: int
13         :rtype: int
14         """
15         day = self.stack_data[-1][1] + 1
16         while price >= self.stack_data[-1][0]:
17             self.stack_data.pop(-1)
18         ans = day - self.stack_data[-1][1]
19         self.stack_data.append([price, day])
20         return ans

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