你会么?我感觉很难---设计数据结构使得均摊成本为O(1)
求解:
有一个real number的set,两个操作:一个是find_min,一个是insert(X),删除的时候
要求是先把小于x的全删除了,然后再插入x,如何借助stack实现一个数据结构,使得两个操作
的均摊成本都是O(1).
[解决办法]
hint是,find_min就return stack.top();
这样的话insert基本就唯一解了。仔细想想就能写出来了。
[解决办法]