algorithm - 具有恒定时间推送和 popmin 的自定义数据结构

Question

我最近在一次采访中遇到了这个问题：
设计一个支持 2 个操作的数据结构：
1. push(N) - 存储一个数字
2. popmin() - 提取所有存储数字的当前最小值并将其从存储中删除

push 和 popmin必须在 O(1) 时间内执行。

起初我想使用 2 个堆栈，但这只允许获得最小数量，而不是删除它。
有任何想法吗？

Answer 1

有很多堆允许在 O(1) 中插入和查找最小值。问题是删除最小值需要 O(log N)。这似乎暗示信息丢失或不正确。