从队列中获取O（1）的最小/最大值？ [英] Get Min/Max in O(1) time from a Queue?

问题描述

如何在0（1）时间复杂度的任何时候从队列中检索max和min元素？
以前我使用Collections.max和min来找到元素，但是将为0（n）。

How can I retrieve the max and min element from a queue at any time in 0(1) time complexity? Earlier I was using Collections.max and min to find the elements but that would be 0(n).

推荐答案

您只能有两种获取O（1）最小/最大操作的方法：

You only have 2 ways to get O(1) for a min/max operation:

• 如果结构被排序，并且您知道如果结构未排序且仅允许插入，则max / min位于


• ：每次插入项目并分别存储值时，可以重新计算最小/最大值


• 如果结构没有排序，并允许插入和删除：我不认为你可以做得比O（n）更好，，除非您使用多个集合（但是该解决方案不支持删除任何元素，只能使用头/尾元素，这应该是队列的情况）。

• if the structure is sorted and you know where the max / min is located
• if the structure is not sorted and only allows insertion: you can recalculate the min / max every time you insert an item and store the value separately
• if the structure is not sorted and allows insertions and removals: I don't think you can do better than O(n), unless you use more than one collection (but that solution does not support removal of any elements, only head / tail elements, which should be the case with a queue).

这篇关于从队列中获取O（1）的最小/最大值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！