Microsoft Stock Price Fluctuation：时间戳修正与惰性堆

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• update(timestamp,price) 可以覆盖既有时间戳；current 是最大时间戳的现行价格，不是最近调用 update 的价格。
• maximum/minimum 只看各时间戳最新有效价格；主代码对无数据查询报错。
• 时间戳和价格为整数；题目未明确范围，Python 可处理大整数。

解题路线

1. 哈希表 by_time 保存每个时间戳的现价，latest 保存目前最大时间戳。
2. 每次 update 将新 (price,timestamp) 推入最小堆，将 (-price,timestamp) 推入最大堆；旧价格项不尝试在堆内部删除。
3. maximum/minimum 查询堆顶时，用 by_time[timestamp] 与堆顶价格比；不相等说明该项是被后续更新覆盖的旧版本，弹掉直到遇到有效项。
4. 每次堆条目最多进一次、出一次，所以惰性删除的弹出总量有界；若更新极多而查询极少，堆会保存很多旧项，可周期重建。

手动走一遍

update(1,10)、update(2,5) 后 current=5、max=10。再 update(1,3) 修正旧时间戳，current 仍是时间 2 的 5；max 查询丢掉旧 (1,10) 后得 5，min=3。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from heapq import heappop, heappush


class StockPrice:
    def __init__(self) -> None:
        self.by_time: dict[int, int] = {}
        self.latest: int | None = None
        self.low: list[tuple[int, int]] = []
        self.high: list[tuple[int, int]] = []

    def update(self, timestamp: int, price: int) -> None:
        self.by_time[timestamp] = price
        self.latest = timestamp if self.latest is None else max(self.latest, timestamp)
        heappush(self.low, (price, timestamp))
        heappush(self.high, (-price, timestamp))

    def current(self) -> int:
        if self.latest is None:
            raise ValueError('no prices')
        return self.by_time[self.latest]

    def maximum(self) -> int:
        if not self.by_time:
            raise ValueError('no prices')
        while self.by_time[self.high[0][1]] != -self.high[0][0]:
            heappop(self.high)
        return -self.high[0][0]

    def minimum(self) -> int:
        if not self.by_time:
            raise ValueError('no prices')
        while self.by_time[self.low[0][1]] != self.low[0][0]:
            heappop(self.low)
        return self.low[0][0]


if __name__ == '__main__':
    prices = StockPrice()
    prices.update(1, 10)
    prices.update(2, 5)
    prices.update(1, 3)
    assert (prices.current(), prices.maximum(), prices.minimum()) == (5, 5, 3)

复杂度

update O(log U) 时间，current O(1)，max/min 均摊 O(log U)（一次查询可能连续清理多个旧条目）；空间 O(U)，U 是 update 次数而非不同时间戳数。要严格限制空间可在旧项比例过高时重建堆。

易错点与追问

容易失分的边界

• 用最近一次 update 的 timestamp 作为 current，而不是最大 timestamp。
• 覆盖价格后仍把旧堆顶当有效最大值。
• 只存每个时间戳最新值，却每次 maximum 线性扫描，达不到题型目标。
• 宣称惰性堆空间只与不同时间戳数成正比。

继续深挖

• 怎样用平衡树/有序多重集做严格 O(D) 级空间？
• 若要查询某个历史版本的最高价，现有覆盖表为何不够？
• 如何处理并发更新同一时间戳的版本排序？