从队列中获取O（1）时间的最小值/最大值？
如何在0（1）时间复杂度的任何时间从队列中检索max和min元素？ 之前我使用Collections.max和min来查找元素，但这将是0（n）。
您只有两种方法可以获得最小/最大操作的O（1）：
- 如果结构已排序，您知道最大/最小位置
- 如果结构未排序且仅允许插入：您可以在每次插入项目时重新计算最小值/最大值并单独存储值
- 如果结构没有排序并允许插入和删除：我认为你不能做得比O（n）更好， 除非你使用多个集合 （但该解决方案不支持删除任何元素，只有头/尾元素，应该是队列的情况）。
存在这样的结构，其作用类似于队列，但允许您在恒定时间内检索最小/最大值，实际上不是严格恒定的，它是分摊的常量时间（可以猜测命名为最小/最大队列）。 有两种方法可以实现它 – 使用两个堆栈或使用队列和双端队列。
Deque实现看起来更像这样（语言不可知）：
所以我们有一个最大元素的双端队列，前面的那个是所需的最大元素，以及一个标准队列。
推动操作
- 如果队列为空，只需按下队列和双端队列上的元素即可。
- 如果队列不为空，则按下队列中的元素，从deque的后面开始删除严格小于我们正在推送的元素的所有元素（它们将不会是最大值，因为推送的元素更大并将在队列中持续更长时间）并将当前元素推送到双端队列的背面
删除操作
- 如果双端队列的前面等于队列的前面，则弹出两个（从前面开始）
- 如果双端队列的前端不等于队列的前面然后只弹出队列，则poped元素肯定不是最大的。
获得最大值
- 它只是双端队列的第一个元素。
（应该添加许多参数以明确其工作原理，但下面提供的第二个版本可能是这种必要性的答案）
Stack实现非常相似，我认为实现起来可能要长一些，但也许更容易掌握。 首先要注意的是，很容易将最大元素存储在堆栈中 – 简单的练习（对于懒惰的 – 使用find-min / find-max的堆栈比O（n）更有效？ ）。 第二部分，如果第一次看到，可能有点棘手，是使用两个堆栈实现队列非常容易，可以在这里找到 – 如何使用两个堆栈实现队列？ 。 基本上就是这样 – 如果我们可以获得两个堆栈的最大元素，我们就可以获得整个队列的最大元素（如果你想要一个更正式的参数，取最大值是关联的或类似的东西，但我打赌你不要不，这很明显。
最小版本以类似方式完成。
一切也可以在O（nlogn）时间内使用一组（或类似的东西）来完成，但它没有意义，因为O（n）中的常量非常小，它应该更快，但更容易实现。
第一版的非有趣部分：
希望我帮了一下。 并希望没有说错。 如果需要，可以在C ++ / C中提供简单的实现。 将不胜感激任何关于表格的反馈，因为这是我在任何地方的第一篇文章:)（英语不是我的母语）。 对正确性的一些确认也会很棒。
编辑：因为这个答案给了我一些观点，我觉得有必要对它进行一点清理，也要稍微扩展一下。
实现一个队列，其中push_rear（），pop_front（）和get_min（）都是常量时间操作
我将存储两个字段minIndex和maxIndex ，它们将分别在数据结构中存储索引位置的最小值和最大值。
将新元素添加到队列时，请检查以下两项内容：
- 元素小于minIndex位置的当前最小元素; 如果是这样，在插入后更新minIndex的值。
- 元素大于maxIndex位置的当前最大元素，并相应地更新引用。
这将为您提供当前最小值和最大值的O（1）渐近线。
这不是一个真正的队列，但你可以实现Min-Max Heap。
http://en.wikipedia.org/wiki/Min-max_heap
基本上，它是一个堆，它具有偶数级别的最大堆属性，以及奇数级别的最小堆属性。
它具有O（1）MIN（）和O（1）MAX（）操作。 然而，迭代相当棘手，但它可以工作并满足您的要求。
我在这里发布完整的代码，以便在一个恒定的时间内在队列中找到MIN和MAX。 如果您有任何疑问，请随时与我联系。
队列
// Queue Interface package com.java.util.collection.advance.datastructure.queue; public interface Queue{ boolean addR(E e); E removeL(); E element(); E elementR(); boolean isFull(); boolean isEmpty(); void trim(); } 双端队列
package com.java.util.collection.advance.datastructure.queue; /** * A deque is a double-ended queue. You can insert items at either end and delete them * from either end. The methods might be called insertLeft() and insertRight(), and * removeLeft() and removeRight(). * @author vsinha * * @param */ public interface DeQueue extends Queue { boolean addL(E element); E removeR(); }
FindMinMaxQueue
package com.java.util.collection.advance.datastructure.queue; @SuppressWarnings("hiding") public interface FindMinMaxQueue extends Queue { public Integer min(); public Integer max(); }
myQueue中
package com.java.util.collection.advance.datastructure.queue; import java.util.Arrays; public class MyQueue implements Queue ,DeQueue { protected int front = 0; protected int rear =-1; protected E[] elements =null; private static final int DEFAULT_INTIAL_CAPACITY =100; private int size =0; public MyQueue(){ this(DEFAULT_INTIAL_CAPACITY); } @SuppressWarnings("unchecked") public MyQueue(int intialCapacity){ if(intialCapacity < 0){ throw new IllegalArgumentException("intial capacity can't be null"); } elements =(E[]) new Object[intialCapacity]; } @Override public boolean addR(E e) { if(! isFull()) { elements[++rear] = e; size++; return true; } return false; } @Override public E removeL() { E element =null; if(!isEmpty()){ element=elements[front]; // Nullify the reference elements[front] =null; ++front; --size; } return element; } @Override public E element() { E element =null; if(!isEmpty()){ element=elements[front]; } return element; } @Override public E elementR() { E element =null; if(!isEmpty()){ element=elements[rear]; } return element; } public boolean isFull() { return rear == elements.length; } public boolean isEmpty() { return size == 0; } Override public String toString() { return "MyQueue [front=" + front + ", rear=" + rear + ", elements=" + Arrays.toString(elements) + ", size=" + size + "]"; } @Override public void trim() { @SuppressWarnings("unchecked") E[] dest =(E[]) new Object[size]; System.arraycopy(elements, front, dest, 0, size); elements = dest; front =0; rear=size-1; } @Override public boolean addL(E element) { if(front != 0) { elements[--front] = element; size++; return true; } return false; } @Override public E removeR() { E element =null; if(size > 0) { element=elements[rear]; // Nullify the reference elements[rear] =null; --rear; --size; } return element; } }
MinAndMaxFinderQueue
package com.java.util.collection.advance.datastructure.queue; public class MinAndMaxFinderQueue extends MyQueue implements FindMinMaxQueue { private Queue maxValuesQueue =null; private Queue minValuesQueue =null; public MinAndMaxFinderQueue (int intialCapacity){ super(intialCapacity); maxValuesQueue =new MyQueue (intialCapacity); minValuesQueue =new MyQueue (intialCapacity); } @Override public boolean addR(Integer e) { if(super.addR(e)){ if(max() == null || max() <= e){ maxValuesQueue.addR(e); } if(min() == null || min() >= e){ minValuesQueue.addR(e); } return true; } return false; } @Override public Integer removeL() { Integer element =super.removeL(); if(element !=null){ if(maxValuesQueue.element() == element){ maxValuesQueue.removeL(); } if(minValuesQueue.element() == element){ minValuesQueue.removeL(); } } //Need to re-generate MIN and MAX queue when the main queue is not empty and min/max queue is empty regenerateMin(); regenerateMax(); return element; } private void regenerateMin(){ Integer current =null; if(!super.isEmpty() && min() ==null){ for(int front = super.front; front<= super.rear;front++){ current = (Integer)elements[front]; if(min() == null || min() >= current){ minValuesQueue.addR(current); } } } } private void regenerateMax(){ Integer current =null; if(!super.isEmpty() && max() ==null){ for(int front = super.front; front<= super.rear;front++){ current = (Integer)elements[front]; if(max() == null || max() <= current){ maxValuesQueue.addR(current); } } } } public Integer min() { return minValuesQueue.elementR(); } public Integer max() { return maxValuesQueue.elementR(); } @Override public String toString() { return super.toString()+"\nMinAndMaxFinderQueue [maxValuesQueue=" + maxValuesQueue + ", minValuesQueue=" + minValuesQueue + "]"; } }
测试
//Test class package com.java.util.collection.advance.datastructure.queue; import java.util.Random; public class MinMaxQueueFinderApp { public static void main(String[] args) { FindMinMaxQueue queue =new MinAndMaxFinderQueue(10); Random random =new Random(); for(int i =0; i< 10; i++){ queue.addR(random.nextInt(100)); System.out.println(queue); System.out.println("MAX :"+queue.max()); System.out.println("MIN :"+queue.min()); } System.out.println(queue); System.out.println("MAX :"+queue.max()); System.out.println("MIN :"+queue.min()); queue.removeL(); System.out.println(queue); System.out.println("MAX :"+queue.max()); System.out.println("MIN :"+queue.min()); queue.removeL(); System.out.println(queue); System.out.println("MAX :"+queue.max()); System.out.println("MIN :"+queue.min()); queue.removeL(); System.out.println(queue); System.out.println("MAX :"+queue.max()); System.out.println("MIN :"+queue.min()); queue.removeL(); System.out.println(queue); System.out.println("MAX :"+queue.max()); System.out.println("MIN :"+queue.min()); queue.removeL(); System.out.println(queue); System.out.println("MAX :"+queue.max()); System.out.println("MIN :"+queue.min()); System.out.println(queue); System.out.println("MAX :"+queue.max()); System.out.println("MIN :"+queue.min()); } }
我怀疑你正在尝试实现PriorityQueue的function。 这是一个排序队列，其中O（log N）得到最低值。 我不确定为什么你想要最大的值，因为队列只有一端。