每日一题 2034. 股票价格波动（中等，有序队列)

思路：

1. 对于最高和最低价格，维护一个有序的存储所有价格的队列即可实现
2. 当执行 update 时，将队列中原来的 price 删除（如果有的话，且耗时O(logn)），然后再插入新的 price 并保持有序（耗时O(logn)），最后更新最新的时间戳
3. 在这里如果采用延迟删除的思想，可以省去一个步耗时O(logn)的删除操作，极大减少最后提交测试的耗时

class StockPrice:

    def __init__(self):
        self.p = {}
        self.cur = 0
        self.l = []

    def update(self, timestamp: int, price: int) -> None:
        if len(self.l) == 0:
            self.l.append(price)
            self.p[timestamp] = price
            self.cur = timestamp
            return

        if timestamp > self.cur:
            self.cur = timestamp
        
        if self.p.get(timestamp, -1) != -1:
            self.l.pop(bisect_left(self.l, self.p[timestamp]))

        self.p[timestamp] = price
        
        insort_left(self.l, price)

    def current(self) -> int:
        return self.p[self.cur]

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

    def minimum(self) -> int:
        return self.l[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32