class MaxQueue {
// 维护一个单调递减的双端队列（队头永远是最大值）
Deque<Integer> deque;
// 使用一个辅助队列来记录所有被插入的值
Queue<Integer> queue;
public MaxQueue() {
deque = new LinkedList<Integer>();
queue = new LinkedList<Integer>();
}
// 求最大值
public int max_value() {
// 队列为空，返回 -1
if (deque.isEmpty())
return -1;
// 返回队头元素，即双端队列中的最大值
return deque.peekFirst();
}
// 插入
public void push_back(int value) {
// 当双端队列不为空，且队尾取出的值比 value 小的时候，不停的让队尾元素出队
// 由于有辅助队列的存在，所以不用担心丢失这些比 value 小的元素
while(!deque.isEmpty() && deque.peekLast() < value)
deque.pollLast();
// 让双端队列中所有比 value 小的元素出队后，就将 value 插入队尾
// 由此来保持双端队列的单调递减
deque.offerLast(value);
// 使用辅助队列来记录所有被插入的值
queue.offer(value);
}
// 删除
public int pop_front() {
// 如果队列为空，返回 -1
if (queue.isEmpty())
return -1;
// 取出辅助队列的队头元素
int ans = queue.poll();
// 如果该元素等于双端队列的最大值，也同时取出双端队列中的队头元素
// 如果该元素不是双端队列中的最大值，可以不用管它
// 单调递减的双端队列的存在只是为了便于求解最大值
if (ans == deque.peekFirst())
deque.pollFirst();
// 返回删除的元素
return ans;
}
}
/**
* 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 Kotlin
class MaxQueue {
// 维护一个单调递减的双端队列（队头永远是最大值）
var deque: Deque<Int>
// 使用一个辅助队列来记录所有被插入的值
var queue: Queue<Int>
init {
deque = LinkedList()
queue = LinkedList()
}
// 求最大值
fun max_value(): Int {
// 队列为空，返回 -1
return if (deque.isEmpty()) -1 else deque.peekFirst()
// 返回队头元素，即双端队列中的最大值
}
// 插入
fun push_back(value: Int) {
// 当双端队列不为空，且队尾取出的值比 value 小的时候，不停的让队尾元素出队
// 由于有辅助队列的存在，所以不用担心丢失这些比 value 小的元素
while (!deque.isEmpty() && deque.peekLast() < value)
deque.pollLast()
// 让双端队列中所有比 value 小的元素出队后，就将 value 插入队尾
// 由此来保持双端队列的单调递减
deque.offerLast(value)
// 使用辅助队列来记录所有被插入的值
queue.offer(value)
}
// 删除
fun pop_front(): Int {
// 如果队列为空，返回 -1
if (queue.isEmpty())
return -1
// 取出辅助队列的队头元素
val ans = queue.poll()
// 如果该元素等于双端队列的最大值，也同时取出双端队列中的队头元素
// 如果该元素不是双端队列中的最大值，可以不用管它
// 单调递减的双端队列的存在只是为了便于求解最大值
if (ans == deque.peekFirst())
deque.pollFirst()
// 返回删除的元素
return ans
}
}
/**
* Your MaxQueue object will be instantiated and called as such:
* var obj = MaxQueue()
* var param_1 = obj.max_value()
* obj.push_back(value)
* var param_3 = obj.pop_front()
*/
3.3 复杂度分析
时间复杂度 O(1) ：删除和求最大值显然为 O(1)。做一次插入操作最多会有 n 次出队操作，但是由于每个数字只会出队一次，所以将出队的时间均摊到每个插入操作上，时间复杂度也为 O(1)。
