一、题目描述
请定义一个队列并实现函数 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(); */
四、时空复杂度分析
时间复杂度： O(1)
空间复杂度： O(N)
