最大栈:链表加有序映射实现
哪些公司问过
答案要点
- 双向链表维护栈顺序,尾部为栈顶,支持 O(1) 删除任意节点
- 有序映射以值为键,存该值对应的节点列表,按入栈顺序排列
- popMax 取最大键列表的最后一个节点,即离栈顶最近的最大值
- pop 和 popMax 都要同步更新链表和映射,列表为空时删除键
- push、pop、peekMax、popMax 为 O(log n),top 为 O(1)
易错点
- 有重复最大值时删错了,应删除离栈顶最近的那个
- 只更新链表忘了同步删除映射中的节点,状态不一致
- 用单向链表导致从中间删除节点需要 O(n)
面试官常见追问
- 两个栈的做法是怎样的?
- 有没有均摊更好的做法?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。