题干与适用场景
实现 MaxStack：push(x) 压入，pop() 删除并返回栈顶，top() 查看栈顶，peekMax() 查看最大值，popMax() 删除并返回最靠近栈顶的最大值。重复最大值必须按后进先出处理；空栈行为要先约定为错误或明确的空值。
公开的 LeetCode 题目和近期面试题记录都采用这组接口。它与只维护前缀最小值的 Min Stack 不同：popMax 需要定位任意位置，并恢复剩余元素的栈顺序。
面试官考察点
- 能否先固定重复最大值的 tie-break 规则和空栈合同。
- 能否解释为什么一个只保存当前最大值的变量无法在最大值被删除后快速恢复。
- 能否把“栈顺序”和“按值找最大值”拆成两个索引，并同步删除同一个节点。
- 能否区分辅助栈的摊销
O(1)方案与平衡树索引的O(log n)方案。
回答前需要澄清的问题
popMax必须是O(1)、摊销O(1)，还是允许O(log n)？这是决定数据结构的核心约束。- 重复最大值删除最靠近栈顶的一个，还是任意一个？不同规则会改变有序索引中的定位方式。
- 是否要求稳定迭代器、并发调用或持久化？这些要求会影响节点生命周期和锁策略。
- 值是可比较对象还是固定整数？固定整数可考虑桶或计数结构，泛型对象通常需要比较树。
30 秒回答框架
“我把每个元素包装成带递增序号的节点。双向链表保持栈顺序；有序索引按 (value, sequence) 排序，最大值位于索引末端。top 读链表尾，peekMax 读索引尾，popMax 从索引尾取出最大值后用节点指针从链表摘除。平衡树方案的 push、pop、peekMax、popMax 都是 O(log n)，top 是 O(1)；如果只要求栈顶操作和 peekMax 为常数，可用辅助最大值栈，但 popMax 需要移动或重建，不能声称仍为 O(1)。”
分步骤深入解答
第一步：把栈顺序和排序顺序分开。
节点包含 value、单调递增的 sequence、prev 和 next。链表尾部是栈顶；有序索引的键为 (value, sequence)，值相同的元素按 sequence 较大者排在后面，因此索引尾部正好是最靠近栈顶的最大值。
第二步：选择可删除的有序索引。
用支持重复键的平衡树、TreeMap 加有序节点集合，或“值到有序序号集合”的两层索引。只保存一个 currentMax 不够：删除当前最大值后必须知道下一个最大值和它对应的节点。
第三步：同步五个操作。
push：创建节点，接到链表尾，并插入有序索引。pop：取链表尾，从有序索引删除同一节点，再摘除链表节点。top：返回链表尾的 value。peekMax：返回有序索引尾节点的 value。popMax：取有序索引尾节点，按指针从链表删除，再从索引删除。
伪代码只展示关键不变量，具体树 API 由语言决定：
node = orderedByValueAndSequence.last()
orderedByValueAndSequence.erase(node.key)
unlink(node.prev, node, node.next)
return node.value第四步：复杂度和替代方案。
平衡树方案的五个操作中，top 是 O(1)，其余涉及索引的操作是 O(log n)，空间为 O(n)。若允许 popMax 摊销 O(n)，可用主栈加辅助最大值栈，把最大值变化记录在每个深度；这更简单，但不能满足高频任意位置删除。
第五步：重复值、空栈和节点一致性。
sequence 既解决重复值排序，也让 popMax 的 tie-break 可证明。空栈操作返回统一错误。每个节点必须只在链表和索引各出现一次；删除时先保存节点引用，再从两个结构同时移除，避免索引悬挂。
第六步：测试顺序与索引。
用慢速数组作为参考模型。测试 [5,1,5] 连续两次 popMax，应依次删除顶部的 5 和底部的 5；覆盖负数、全相等值、空栈、交替 push/pop、最大值位于中间、重复删除和随机长序列。每次操作后同时验证链表顺序、索引大小和 peekMax 结果。
高质量示范回答
“我会用双向链表保存栈顺序，再用按 (value, sequence) 排序的平衡索引定位最大节点。sequence 单调递增，所以重复最大值中序号最大的就是离栈顶最近的一个。每个节点同时保存链表指针和索引键：pop 从链表尾取节点，popMax 从索引尾取节点，然后都从另一结构删除同一节点。这样 top 是 O(1)，其余操作是 O(log n)，空间 O(n)。如果面试官只要求 peekMax 而不要求任意位置删除，我会改用辅助最大值栈，减少实现复杂度。”
常见错误
- 只保存一个当前最大值 → 删除最大值后不知道下一个最大值 → 维护可查询的有序索引。
- 把 popMax 当成 pop → 删除了错误位置，栈顺序被改变 → 按索引找节点，再按链表指针摘除。
- 重复最大值不带序号 → 无法证明删除最靠近栈顶的那个 → 键使用
(value, sequence)。 - 索引删除后忘记链表节点 → 后续 top 读到已删除对象 → 两个结构引用同一节点并原子更新。
- 把辅助栈方案写成 popMax O(1) → 任意位置删除通常要搬移元素或重建索引 → 明确写出摊销或最坏复杂度。
追问及应对
追问 1：能否让所有操作都达到 O(1)？
若值是固定宽度整数，可以研究桶或专用整数优先结构，但复杂度会依赖值域宽度、内存和实现模型。对任意可比较对象，面试中应诚实给出 O(log n) 索引方案，而不是把均摊、期望和最坏界限混在一起。
追问 2：如何改成线程安全版本？
最简单的合同是让五个复合操作由同一把锁保护，保证链表和有序索引不会短暂分叉。更高并发需要分片或不可变快照，但 popMax 涉及两个结构的原子删除，不能只分别加锁后假设一致。
追问 3：如果只需要 peekMax，不需要 popMax 呢？
用主栈加同长度的前缀最大值栈。push 同时记录当前最大值，pop 同时弹出两栈，top 和 peekMax 读取各自栈顶，所有操作都是 O(1)；重复最大值必须重复记录。