TikTok MaxStack：栈序、最大序与懒删除

题意与假设

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

• 训练提供 push/pop/top/peekMax/popMax，同最大值时删最新入栈项。实际 API 与同值规则未给，练习前确认。

解题路线

1. 双链表维护栈次序，节点能常数 unlink；最大堆按(-value,-sequence) 排序，sequence 唯一，平值优先新项。
2. 普通 pop 从链尾移除并标 dead，堆暂留该项；peekMax/popMax 先从堆顶清理 dead，再读取或移除 alive 节点。
3. 每个入堆项最多被清理一次，摊还堆操作可分析；单次查询可能遇到很多过期项，不能保证严格 O(log n)。
4. 堆可能长时间保留非顶 dead 项，空间依历史 push 数，而非仅当前活跃大小。定期重建或使用可删除有序索引才控制长期空间。

手动走一遍

push5,1,5，popMax 删除第二个5，栈剩5,1，top=1；再次 peekMax=5。频繁 pop 低值留下 dead 堆项，下次高值被弹后可能连续清理，产生延迟峰值。

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

复杂度

T 次历史插入下，push O(log T)，top/pop O(1)，堆查询/删除摊还 O(log T)，单次清理最坏 O(T log T)；空间 O(T)，不承诺仅 O(当前n)。

易错点与追问

容易失分的边界

• 同值删旧项。
• 未清理 dead 堆顶。
• 懒删除空间写成严格当前 O(n)。

继续深挖

• 如何用平衡树得到可控删除？
• 何时触发 heap 重建？