【Python】詳解 bisect 模塊_聞韶-CSDN博客
5896. 股票價格波動
class StockPrice(object):
def __init__(self):
self.cur=[0,0]
self.price=[]
self.time={}
def update(self, timestamp, price):
"""
:type timestamp: int
:type price: int
:rtype: None
"""
#如果時間戳大於當前時間
if timestamp>=self.cur[0]:
self.cur=[timestamp, price]
#把price插入到price列表裡
#如果timestamp以前出現過
if timestamp in self.time:
#刪掉這個時間戳下以前的價格
self.price.remove(self.time[timestamp])
bisect.insort(self.price,price)
self.time[timestamp]=price
def current(self):
"""
:rtype: int
"""
return self.cur[1]
def maximum(self):
"""
:rtype: int
"""
return self.price[-1]
def minimum(self):
"""
:rtype: int
"""
return self.price[0]
# Your StockPrice object will be instantiated and called as such:
# obj = StockPrice()
# obj.update(timestamp,price)
# param_2 = obj.current()
# param_3 = obj.maximum()
# param_4 = obj.minimum()class StockPrice:
def __init__(self):
self.stock = {}
self.max_stock = []
self.min_stock = []
self.timestamp = 0
def update(self, timestamp: int, price: int) -> None:
self.timestamp = max(timestamp,self.timestamp)
self.stock[timestamp] = price
heapq.heappush(self.max_stock,(-price,timestamp))
heapq.heappush(self.min_stock,(price,timestamp))
def current(self) -> int:
return self.stock[self.timestamp]
def maximum(self) -> int:
while -self.stock[self.max_stock[0][1]]!=self.max_stock[0][0]:
heapq.heappop(self.max_stock)
return -self.max_stock[0][0]
def minimum(self) -> int:
while self.stock[self.min_stock[0][1]]!=self.min_stock[0][0]:
heapq.heappop(self.min_stock)
return self.min_stock[0][0]
用大小頂堆來做
class StockPrice:
def __init__(self):
#用兩個最小堆存儲價格。python裡是最小堆
self.min_heap=[]
self.max_heap=[]
#這個存儲當前有效的時間戳和價格
self.timestamp_price={}
#用這個存儲股票的最新時間
# self.timestamp=[]
self.max_timestamp=0
def update(self, timestamp: int, price: int) -> None:
#如果沒在kv裡，說明首次出現。如果在裡面，也不用修改。因為這個數組存貯的是時間，修改的是時間下的價格。
# if timestamp not in self.timestamp_price:
# self.timestamp.append(timestamp)
if timestamp>self.max_timestamp:
self.max_timestamp=timestamp
self.timestamp_price[timestamp]=price
#最小堆
heapq.heappush(self.min_heap,(price,timestamp))
#最大堆
heapq.heappush(self.max_heap,(-price,timestamp))
def current(self) -> int:
return self.timestamp_price[self.max_timestamp]
def maximum(self) -> int:
while self.timestamp_price[self.max_heap[0][1]]!=-self.max_heap[0][0]:
# self.max_heap.pop()
heapq.heappop(self.max_heap)
return -self.max_heap[0][0]
def minimum(self) -> int:
#如果最小價格和時間戳，出現在了self.timestamp_price裡，說明是最新的
#如果沒出現，說明這個值已經被更新了。pop出去
while self.timestamp_price[self.min_heap[0][1]]!=self.min_heap[0][0]:
# self.min_heap.pop()
heapq.heappop(self.min_heap)
return self.min_heap[0][0]
