面试题库 › C++ / 后端 › 最大栈:链表加有序映射实现

最大栈:链表加有序映射实现

难度 ★★★在 1 场真实面经中被问到 方向:C++ / 后端考点:数据结构设计

哪些公司问过

快手1

常见岗位:C/C++ 软件开发

答案要点

  1. 双向链表维护栈顺序,尾部为栈顶,支持 O(1) 删除任意节点
  2. 有序映射以值为键,存该值对应的节点列表,按入栈顺序排列
  3. popMax 取最大键列表的最后一个节点,即离栈顶最近的最大值
  4. pop 和 popMax 都要同步更新链表和映射,列表为空时删除键
  5. push、pop、peekMax、popMax 为 O(log n),top 为 O(1)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题