[数据结构与算法]leetcode:股票价格波动

思路：
数据的快速改查增记录max、min、current

我的超时无脑模拟

class StockPrice:

    def __init__(self):
        # 来个map记录每个时刻对应的index
        self.myMap = defaultdict(int)
        self.myList = []
        # 最大值
        self.maxPrice = -1
        # 最小值
        self.minPrice = 0x7f7f7f7f
        # 最新时间
        self.latestTime = -1
        # 最新价格
        self.lastestPrice = -1


    def update(self, timestamp: int, price: int) -> None:
        
        if timestamp not in self.myMap:
            self.myList.append(price)
            index = len(self.myList) - 1
            self.myMap[timestamp] = index
        else:
            self.myList[self.myMap[timestamp]] = price
        # 最新价格
        if timestamp >= self.latestTime:
            self.latestTime = timestamp
            self.lastestPrice = price



    def current(self) -> int:
        return self.lastestPrice


    def maximum(self) -> int:
        return max(self.myList)


    def minimum(self) -> int:
        return min(self.myList)



# 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()

官方答案

from sortedcontainers import SortedList

class StockPrice:

    def __init__(self):
        # Sortedlist 自动排序！
        self.price = SortedList()
        self.timePriceMap = {}
        self.maxTimestamp = 0
        


    def update(self, timestamp: int, price: int) -> None:
        # 辞旧
        if timestamp in self.timePriceMap:
            self.price.discard(self.timePriceMap[timestamp])
        # 迎新
        self.price.add(price)
        self.timePriceMap[timestamp] = price
        self.maxTimestamp = max(self.maxTimestamp, timestamp)


    def current(self) -> int:
        return self.timePriceMap[self.maxTimestamp]


    def maximum(self) -> int:
        return self.price[-1]


    def minimum(self) -> 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()

总结：
from sortedcontainers import SortedList