题目重点：双链表维护栈序、最大堆维护值序；解释 popMax 低频时为何线性扫描可能更划算。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练接口是 push/pop/top/peek_max/pop_max；同一最大值有多个时 pop_max 删最近压入的那个，空栈抛 IndexError。具体规则按常见 MaxStack 练习设定，不能说是题目明示。
- 输入值为整数；训练实现用链表节点 alive 与最大堆惰性清理，堆项按 (-value,-push_sequence) 排序。
解题路线
- 普通栈顶操作靠双链表尾端 O(1)；每次 push 创建节点并向最大堆放一项。pop 把链表尾节点标 dead，暂不从堆随机删除。
- peekMax/popMax 先清理堆顶已 dead 的节点；最大堆按值降序、压入序号降序保证同值删最近者。popMax 弹堆顶后从链表 O(1) unlink。
- 惰性清理每个节点最多从堆弹一次，所以堆维护摊还 O(log N)；但如果 popMax 很少，堆每次 push 的 O(log N) 与额外内存可能不值得。简化为单链表/数组栈，popMax 时线性扫描最大值及最近位置，O(N)，其它操作 O(1)。
- 若业务明确要求所有操作最坏 O(log N) 或 O(1)，需选有序映射/平衡树加每值节点链表；Python 标准库没有直接的平衡树，不能用普通 dict 假装排序。
手动走一遍
依次 push 5、1、5：top=5、peekMax=5；popMax 删除后压入的 5，top 变 1。再 pop 返回 1，旧堆中的 1 节点变 stale，下一次 peekMax 会清掉它。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
import heapq
class _Node:
def __init__(self, value, sequence):
self.value = value
self.sequence = sequence
self.prev = self.next = None
self.alive = True
class MaxStack:
def __init__(self):
self.head = _Node(None, -1)
self.tail = _Node(None, -1)
self.head.next = self.tail
self.tail.prev = self.head
self.heap = []
self.sequence = 0
def _unlink(self, node):
node.prev.next = node.next
node.next.prev = node.prev
node.alive = False
def push(self, value: int):
self.sequence += 1
node = _Node(value, self.sequence)
previous = self.tail.prev
previous.next = node
node.prev, node.next = previous, self.tail
self.tail.prev = node
heapq.heappush(self.heap, (-value, -node.sequence, node))
def top(self) -> int:
if self.tail.prev is self.head:
raise IndexError("empty stack")
return self.tail.prev.value
def pop(self) -> int:
node = self.tail.prev
if node is self.head:
raise IndexError("empty stack")
self._unlink(node)
return node.value
def _prune(self):
while self.heap and not self.heap[0][2].alive:
heapq.heappop(self.heap)
def peek_max(self) -> int:
self._prune()
if not self.heap:
raise IndexError("empty stack")
return -self.heap[0][0]
def pop_max(self) -> int:
self._prune()
if not self.heap:
raise IndexError("empty stack")
_, _, node = heapq.heappop(self.heap)
self._unlink(node)
return node.value
复杂度
push O(log N)，pop/top O(1)，peekMax/popMax 摊还 O(log N)，活节点+陈旧堆项 O(累计 push 数) 空间，需定期重建才能压回 O(N_active)。低频 popMax 的线性扫描版本 push/pop O(1)、popMax O(N)。3,000 组随机操作序列与列表 oracle 对照。
易错点与追问
容易失分的边界
- 同值 popMax 删除最早的最大值而非最近的。
- pop 后堆项未标 stale，后续 peekMax 返回已删节点。
- 声称惰性堆空间永远 O(当前栈长)。
- popMax 低频仍不讨论简单 O(N) 方案。
- 用 hash 表宣称可直接获得当前最大 key。
继续深挖
- popMax 只占 0.1% 调用时怎样选结构？
- 如何在堆陈旧项过多时重建？
- 需要支持并发 push/popMax 怎么锁？
- 若值范围小且固定，能否用桶优化？
