TikTok MinStack：前缀最小值与重复最小项

题意与假设

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

• 基础合同 push/pop/top/minimum，空栈读取抛错；训练目标最小查询 O(1)。
• 复杂度文字有歧义，本文不据其断言原要求；动态数组 push/pop 是摊还常数。

解题路线

1. 每个栈项存(value,当前前缀minimum)。push 的新最小=min(value,旧最小)，pop 同时去掉该层值与摘要。
2. 最小查询只读顶层摘要，历史状态已随栈保存；重复最小值各层独立，因此弹一个重复项仍保留另一项。
3. 也可双栈只记更小/相等项，但相等时必须正确计数或重复压入。差值编码需考虑整数范围与溢出，不默认更安全。
4. 最小是顺序统计的一端，维护它不等于能从任意位置删最小；若加 popMin 需要索引与删除结构。

手动走一遍

push3,1,1,2，minimum=1；pop2和pop1后仍1；再pop1后恢复3。空栈 min/pop 明确错误，不用0作为缺失哨兵。

Python 参考实现

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

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

class MinStack:
    def __init__(self):
        self._values = []
    def push(self, value):
        minimum = min(value, self._values[-1][1]) if self._values else value
        self._values.append((value, minimum))
    def pop(self):
        if not self._values:
            raise IndexError('empty stack')
        return self._values.pop()[0]
    def top(self):
        if not self._values:
            raise IndexError('empty stack')
        return self._values[-1][0]
    def minimum(self):
        if not self._values:
            raise IndexError('empty stack')
        return self._values[-1][1]

复杂度

min/top O(1)，动态数组 push/pop 摊还 O(1)，O(n) 空间；如严格最坏需另选合适节点存储。

易错点与追问

容易失分的边界

• 弹一个重复最小后丢掉所有最小。
• 每次 query 扫描却声称常数。
• 0 当空栈结果与真实0冲突。

继续深挖

• 只用一个整数保存 min 为什么不够？
• 最小和最大同时维护如何扩展？