python_ Use of bisect module

【Python】 Detailed explanation bisect modular _ Wen Shao -CSDN Blog

5896. Stock prices fluctuate

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 the timestamp is greater than the current time
if timestamp>=self.cur[0]:
self.cur=[timestamp, price]
# hold price Insert into price In the list
# If timestamp There have been... Before
if timestamp in self.time:
# Delete the time stamp and put down the previous price
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]

Use the big and small top piles to do

class StockPrice:
def __init__(self):
# Use two minimum heaps to store prices .python Is the smallest heap
self.min_heap=[]
self.max_heap=[]
# This stores the currently valid timestamp and price
self.timestamp_price={}
# Use this to store the latest time of the stock
# self.timestamp=[]
self.max_timestamp=0
def update(self, timestamp: int, price: int) -> None:
# If not in kv in , Explain the first occurrence of . If it's inside , You don't have to modify it . Because this array stores time , What is modified is the price under time .
# 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
# The smallest pile
heapq.heappush(self.min_heap,(price,timestamp))
# The biggest pile
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:
# If the minimum price and timestamp , Appear in self.timestamp_price in , The instructions are up to date
# If it doesn't show up , This indicates that the value has been updated .pop get out
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]