Bloomberg Equity Tracker：追加/撤销最新价格与 O(1) 查询

题意与假设

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

• update 是按时间追加新价格，remove 只撤销最近一次更新；若可修改任意历史日期，O(1) max 方案不适用。
• 空序列返回值题目未说，训练版返回 None；价格有限，平均值可用浮点展示，真实金融金额需 Decimal/定点数。

解题路线

1. prices 栈记录顺序，maxima[i] 记录前 i+1 次更新中的最大值，total 记录当前价格总和。
2. 追加 price 时 push price、push max(price, oldMax)，并增加 total；撤销最新价时同步弹两个栈并减去该价。
3. latest 查栈顶，max 查 maxima 栈顶，average=total/长度；每次读 O(1)，两个栈长度一致是不变量。
4. LC 295 式中位数可用双堆支持插入 O(log n)、查询 O(1)，但撤销最新还需删除标记/索引或可回滚平衡树；不能声称保持所有操作 O(1)。

手动走一遍

依次更新 100、120、90：maxima=[100,120,120]，total=310，average=310/3。撤销 90 后 latest=120、max=120、average=110；再撤销 120 后 max 回到 100。

Python 参考实现

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

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

class EquityTracker:
    """Latest/max/average after append and pop-latest; prices are finite."""

    def __init__(self):
        self.prices = []
        self.maxima = []
        self.total = 0

    def update(self, price):
        self.prices.append(price)
        self.maxima.append(price if not self.maxima else max(price, self.maxima[-1]))
        self.total += price

    def remove_latest(self):
        if not self.prices:
            return None
        self.maxima.pop()
        price = self.prices.pop()
        self.total -= price
        return price

    def latest(self):
        return self.prices[-1] if self.prices else None

    def maximum(self):
        return self.maxima[-1] if self.maxima else None

    def average(self):
        return self.total / len(self.prices) if self.prices else None

复杂度

所述 append/pop/latest/max/average 均 O(1) 时间、O(n) 空间；若任意历史点删除或求中位数，复杂度另议。

易错点与追问

容易失分的边界

• 只保留全局 max，删掉最新最大值后无法恢复旧最大。
• remove 非最新价仍套双栈。
• 空序列除以零。
• 将浮点平均值用于真实货币结算。

继续深挖

• 如果一个价要按日期更新怎么办？
• 多只 equity 怎样分片和并发？
• 中位数能否保持 O(1)？
• 撤销后审计历史需要怎样保留？