我遇到了这个问题:实现一个队列,使得push_rear()、pop_front()和get_min()的时间复杂度都为常数级别。
我最初想到使用最小堆数据结构来实现get_min(),因为它的复杂度为O(1)。但是push_rear()和pop_front()的复杂度将会是O(log(n))。
有人知道如何实现这样的队列吗?需要同时实现O(1)的push()、pop()和min()?
我搜索了一下,想指出这个Algorithm Geeks的帖子,但似乎没有一种解决方案能够满足所有3个方法的常数时间规则:push()、pop()和min()。
谢谢大家的建议。
有人知道如何实现这样的队列吗?需要同时实现O(1)的push()、pop()和min()?
我搜索了一下,想指出这个Algorithm Geeks的帖子,但似乎没有一种解决方案能够满足所有3个方法的常数时间规则:push()、pop()和min()。
谢谢大家的建议。