队列中的最大值

题目: https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

需要一个双端队列 作为辅助队列

在每次入队时，如果 deque 队尾元素小于即将入队的元素 value，则将小于 value 的元素全部出队后，再将 value 入队；否则直接入队。

LeetCode官方的例子：
如果我们向队列中插入数字序列 1 1 1 1 2，那么在第一个数字 2 被插入后，数字 2 前面的所有数字 1 将不会对结果产生影响。因为按照队列的取出顺序，数字 2 只能在所有的数字 1 被取出之后才能被取出，因此如果数字 1 如果在队列中，那么数字 2 必然也在队列中，使得数字 1 对结果没有影响的。

class MaxQueue {
    Queue<Integer> queue = null;
    Deque<Integer> help = null;
    public MaxQueue() {
        queue = new LinkedList<>();
        help = new LinkedList<>();
    }
    
    public int max_value() {
        //直接返回最上面的元素
        if(help.isEmpty())
            return -1;
        //返回的help队列最前面的值
        return help.peekFirst();
    }
    
    public void push_back(int value) {
        queue.offer(value);
        //保持help队列从大到小
        while(!help.isEmpty() && value > help.peekLast()){
            help.pollLast();
        }
        help.addLast(value);
    }
    
    public int pop_front() {
       //先进先出
       if(queue.isEmpty()) return -1;
       int e = queue.poll();
       //剔除help队列中的有关元素
       while(!help.isEmpty() && e == help.peekFirst()){
           help.pollFirst();
       }
       return e;
    }
}

/**
 * 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();
 */
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
36
37
38
39
40
41
42
43
44