一、题目描述

请定义一个队列并实现函数 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：

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

限制：

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

二、思路讲解

这其实容易想到：包含min函数的栈（剑指offer 30）_玉面大蛟龙的博客-CSDN博客

根据这个思路，可以想到用一个队列new_queue，他的队头元素永远是queue中的最大值。但是两个题有一定的区别，区别主要是源于栈和队列的本质区别。假如我们将队头最大值出队列之后，就无法判断次最大值了。

所以我们需要用一个单调递减的队列，保证这个队列中的值从头到尾是递减的。那么队头元素即是最大值，他出队列之后，此时队头元素是次最大值。

那么如何维护这个单调递减队列呢？

一、当我们入队列时：

1、如果单调队列为空，直接入队列；

2、如果入队列的元素大于队头元素，说明他大于队列中所有元素，就将它放到头部；

3、如果入队列元素小于队头元素，那就从队尾开始，将小于它的元素依次出队尾，再把该元素入队尾。

二、当我们出队列时：

1、如果队列中要出的元素和单调队列中的队头元素相等，说明要出最大的元素，那么将单调队列队头元素出列；

2、如果队列中要出的元素小于单调队列中的队头元素，说明要出的元素不是最大值，就不需要改变单调队列，此时单调队列队头元素仍是最大值。

三、当我们要看最大值时：

直接看单调队列的队头即可。

综上所述，能够完成这个单调队列功能的必须是一个双端队列，所以，我们使用双端队列完成这个单调队列。

三、Java代码实现

class MaxQueue {

    Queue<Integer> queue;   //题目要求定义的队列
    Deque<Integer> deque;   //单调双端队列

    public MaxQueue() {
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }
    
    public int max_value() {
        if(queue.size() == 0){
            return -1;
        }
        //直接看单调队列的队头
        return deque.peekFirst();
    }
    
    public void push_back(int value) {
        queue.add(value);
        //把小于value的元素依次从队尾出队列，保证递减
        while(deque.size()!=0 && deque.peekLast()<=value){
            deque.pollLast();
        }
        deque.add(value);       
    }
    
    public int pop_front() {
        if(queue.size() == 0){
            return -1;
        }
        int temp = queue.poll();
        //如果要出的是最大值，就把单调队列的头出队列；否则不用管
        if(temp == deque.peekFirst()){
            deque.pollFirst();
        }
        return temp;
    }
}

/**
 * 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();
 */