题目描述

解题思路

对于普通队列，入队 push_back() 和出队 pop_front() 的时间复杂度均为 O(1) ；本题难点为实现查找最大值 max_value() 的 O(1) 时间复杂度。 假设队列中存储 N 个元素，从中获取最大值需要遍历队列，时间复杂度为 O(N) ，单从算法上无优化空间。

如下图所示，最直观的想法是 维护一个最大值变量 ，在元素入队时更新此变量即可；但当最大值出队后，并无法确定下一个 次最大值 ，因此不可行。
所以需要一个递减的队列来维护最大值，如果取最大值就直接返回，此时时间复杂度O(1)，就是空间换时间。
为了实现此递减列表，需要使用 双向队列 ，假设队列已经有若干元素：

• 当执行入队 push_back() 时： 若入队一个比队列某些元素更大的数字 xx ，则为了保持此列表递减，需要将双向队列 尾部所有小于 xx 的元素 弹出。
• 当执行出队 pop_front() 时： 若出队的元素是最大元素，则 双向队列 需要同时 将首元素出队 ，以保持队列和双向队列的元素一致性。

使用双向队列原因：维护递减列表需要元素队首弹出、队尾插入、队尾弹出操作皆为 O(1) 时间复杂度。

使用大小堆是不符合此题，需要自定义队列，自定义的队列和滑动窗口最大值一致。

class MaxQueue {
    Deque<Integer> quque;
    MyQueue myQueue;
    public MaxQueue() {
        quque = new LinkedList<>();
        myQueue = new MyQueue();
    }
    public int max_value() {
        if (quque.isEmpty()) return -1;
        return myQueue.peek();
    }
    public void push_back(int value) {
        quque.add(value);
        myQueue.push(value);
    }
    public int pop_front() {
        if (quque.isEmpty()) return -1;
        myQueue.poll(quque.peek());
        return quque.poll();
    }
    class MyQueue {
        Deque<Integer> deque = new LinkedList<>();
        void push(int val) {
            while (!deque.isEmpty() && deque.getLast() < val) {
                deque.removeLast();
            }
            deque.add(val);
        }
        void poll(int val) {
            if (!deque.isEmpty() && deque.peek() == val) {
                deque.poll();
            }
        }
        int peek() {
            return deque.peek();
        }
    }
}