设计支持 insert、min、max 的高效容器
哪些公司问过
答案要点
- 只有插入时,两个变量维护最小、最大值,全部 O(1)
- 任意删除:平衡树或有序多重集合,插入删除 O(log n)
- 双堆 + 延迟删除也可支持任意删除
- 队列语义:两个单调双端队列,均摊 O(1)
- 栈语义:辅助栈记录每层的最小、最大值,O(1)
易错点
- 不问清是否有删除操作就直接给出复杂方案
- 只用变量记录最值,却声称支持删除
- 单调队列入队时弹出条件写反,破坏单调性
面试官常见追问
- 单调队列为什么是均摊 O(1)?
- 双堆延迟删除怎么实现?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。