目录

• 题目信息
• 样例
• • • • • 示例 1：
        • 示例 2：
• 限制条件
• 思路：
• • Step 1：
  • Step 2：
  • Step 3：
  • Step 4：
  • 总结：
  • 代码实现

题目信息

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

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

样例

示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

示例 2：

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制条件

限制：

1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5

思路：

题目要求插入、删除、和求最大值的均摊时间复杂度都是O(1)。插入和删除很简单。关键是怎么做到时间复杂度是O(1)的求最大值，如果是暴力的话，求最大值就需要遍历一遍队列元素，那样的时间复杂度的O（n）的。

接下来我用空间换时间的做法，在多引入一个双端队列来辅助 求最大值。

接下来用一组数据举一个例子：3 4  1  5

Step 1：

Step 2：

Step 3：

Step 4：

总结：

在插入的时候，可以发现，任何时候的max都可以在双端队列的队头直接获得，因此就实现了时间复杂度O(1)的求max。

代码实现

接下来看看具体实现的代码，制作不易，看明白了给个三连可好？

class MaxQueue {
    //q是普通队列，d是双端队列
Queue<Integer> q;
Deque<Integer> d;

    public MaxQueue() {
        //初始化
        
        q=new LinkedList<> ();
        d=new LinkedList<> ();
    }

    public int max_value() {
        //如果双端队列为空返回-1，不然就返回双端队列的队头元素
        if(d.isEmpty ()){
            return -1;
        }
        return  d.peekFirst ();
    }

    public void push_back(int value) {
        //当双端队列不为空并且它的队尾元素<待插入元素时，将队头元素出队列
        while (!d.isEmpty () && d.peekLast ()<value){
            d.pollLast ();
        }
        //两个条件有一个不满足的话，正常插入
        d.offerFirst (value);
        q.offer (value);
    }

    public int pop_front() {
        //普通队列为空返回-1
        if (q.isEmpty ()){
            return  -1;
        }
        //先获取普通队列的队头，如果队头和双端队列的队列相等的话，那么双端队列的队列也要出队列。
        int ans=q.poll ();
        if(ans==d.peekFirst ()){
            d.pollFirst ();
        }
        return  ans;
    }
}