使用 max() API 实现队列，以便 push()、pop() 和 max() (摊销)O(1) 中的所有工作都是 known solved problem 。是否有已知的解决方案可以使用相同的 max() API 实现比 O(n) 更快的双端队列？能证明这是不可能的吗？
最佳答案
100% 可能有一个 deque 和 O(1) max api。
双端队列可以是 implemented from two stacks 。虽然需要一些额外的业务逻辑来保持双端队列平衡，但这个想法相当简单。想象一下面向相反方向的两个堆栈连接在一起。从这个结构中，您可以弹出并附加到两侧。
可以创建一个具有恒定时间 get_max() 或 get_min() 的堆栈。每次插入堆栈时，都会插入两件事 - (value, current_max)。您可以通过将前一个元素中的 current_max 与当前值 进行比较来计算恒定时间内的 current_max。 get_max() 的结果将始终是堆栈顶部的 current_max。
如果您从具有 get_max() api 的两个堆栈实现一个 deque，要获取双端队列的最大值，您只需调用 get_max( ) 对于两个堆栈并返回较大的值。
关于data-structures - 具有最大 api 的双端队列？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54609918/