本文共 1360 字，大约阅读时间需要 4 分钟。

题目：请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入:

输入:

限制：

1 <= push_back,pop_front,max_value的总操作数 <= 10000

答案：

class MaxQueue {
   //一个正常队列，一个优先队列    private Queue
   
     queue;    private Queue
    
      minHeap;     public MaxQueue() {
           queue = new LinkedList<>();        minHeap = new PriorityQueue<>(new Comparator
     
      () {
               @Override            public int compare(Integer o1, Integer o2) {
                   return o2 - o1;            }        });    }        public int max_value() {
           if(minHeap.isEmpty()) return -1;        return minHeap.peek();    }        public void push_back(int value) {
           queue.add(value);        minHeap.add(value);    }        public int pop_front() {
           if(queue.isEmpty()) return -1;        minHeap.remove(queue.peek());        int num = queue.poll();        return num;    }}/** * Your MaxQueue object will be instantiated and called as such: * MaxQueue obj = new MaxQueue(); * int param_1 = obj.max_value(); * obj.push_back(value); * int param_3 = obj.pop_front(); */
     
    
   

转载地址：https://darkness.blog.csdn.net/article/details/115656673 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！