用单调队列实现队列最大值的快速查找

题目链接-来源：力扣（LeetCode）

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

思路：

受前一题启发，前一题的数据工作集是一个「滑动窗口」，而本题的工作集是一个「队列」，较新的元素在一侧，而较旧的元素在另一侧，结构上而言是相似的，因此可以直接套用前一题的思路。
max_value 其实就相当于前一题的「滑动窗口」中的最大值，而其余功能都是队列基本的功能。于是我们只需定义一个主队列存储元素，再定义一个「单调队列」辅助查找最大值即可。
时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class MaxQueue {
    Deque<Integer> monoD;
    Queue<Integer> q;
    
    public MaxQueue() {
        monoD = new LinkedList<>();
        q = new LinkedList<>();
    }
    
    public int max_value() {
        if (q.isEmpty()) {
            return -1;
        }
        return monoD.peekFirst();
    }
    
    public void push_back(int value) {
        q.offer(value);
        while (!monoD.isEmpty() && value > monoD.peekLast()) {
            monoD.pollLast();
        }
        monoD.offerLast(value);
    }
    
    public int pop_front() {
        if (q.isEmpty()) {
            return -1;
        }
        int pop = q.poll();
        if (pop == monoD.peekFirst()) {
            monoD.pollFirst();
        }
        return pop;
    }
}