我最近在面试中遇到了这个问题:
设计一个数据结构,支持以下两个操作: 1. push(N) - 存储一个数字 2. popmin() - 提取所有存储数字中的最小值,并从存储中删除它 push和popmin操作都必须在O(1)时间内执行。
起初我考虑使用两个栈,但这只能获取最小数,无法移除它。
有什么想法吗?
设计一个数据结构,支持以下两个操作: 1. push(N) - 存储一个数字 2. popmin() - 提取所有存储数字中的最小值,并从存储中删除它 push和popmin操作都必须在O(1)时间内执行。
起初我考虑使用两个栈,但这只能获取最小数,无法移除它。
有什么想法吗?
O(1)
的push
和pop_min
的数据结构将允许构建一个O(n)
的排序算法。众所周知,基于比较的排序的最佳情况是O(n*log(n))
... - Darren Engwirda