1.题目

2.分析

使用O(1) 时间复杂度来获得队列或栈的最大值或者最小值，往往需要使用一个辅助的数据结构实现，具体选用何种数据结构需要在做题过程中总结规律。

push_back和pop_front，用普通的双端队列就可以实现O(1)。 对于max_value，需要保证队首元素始终最大，可用一个辅助的单调队列实现(内部元素递减)。

①队列为空，直接添加到队尾；队列不为空，继续②； ②队列最后一个元素(peekLast)大于当前元素，将当前元素添加到队尾； ③队列最后一个元素(peekLast)小于当前元素，先将小于当前元素的全部出队，再将当前元素入队。 可参见上一题

3.代码

3.1 我的代码好慢啊

本题辅助队列可以是单调递减，也可以是非递增（相等元素都放入）。 这里我还是有些疑惑的。。。

class MaxQueue { LinkedList<Integer> a,b; public MaxQueue() { a=new LinkedList<>(); b=new LinkedList<>(); } //求最大值 public int max_value() { if(a.isEmpty()) return -1; return b.peekFirst(); } //a队尾添加 public void push_back(int value) { a.addLast(value); add(value); } //a队首弹出 public int pop_front() { if(a.isEmpty()) return -1; Integer v=a.removeFirst(); if(v.equals(b.peekFirst())) b.pollFirst(); return v; } //添加到b public void add(int i){ //b为空 if(b.isEmpty()){ b.addLast(i); } //b不为空 else{ //2.b队尾元素 大于i if(b.peekLast()>i){ b.addLast(i); } //3.b队尾元素 小于等于i else{ while(!b.isEmpty()&&b.peekLast()<=i){ b.removeLast(); } b.addLast(i); } } } } /** * 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(); */

3.2 提交用时最短的代码

啊这…直接比较？

class MaxQueue { int[] q = new int[20000]; int begin = 0; int end = 0; int maxValue = -1; public MaxQueue(){ } public int max_value(){ if(begin == end) { return -1; } return maxValue; } public void push_back(int value) { q[end++] = value; maxValue = Math.max(maxValue,value); } public int pop_front(){ if(begin == end) { return -1; } int value = q[begin]; if(value == maxValue) { maxValue = q[begin+1]; for(int i = begin+1;i<=end;i++){ maxValue = Math.max(maxValue,q[i]); } } begin++; return value; } } /** * 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(); */

4.复杂度

均摊时间复杂度:三个操作均为O(1)。 push_back：O(1)，例如 543216，只有最后一次 push_back 操作是O(n)，其他每次操作的时间复杂度都是O(1)，均摊时间复杂度为 (O(1)×(n−1)+O(n))/n=O(1)。

空间复杂度O(N)