剑指 Offer 59 - II. 队列的最大值

class MaxQueue {
    
    Queue<Integer> q;
    Deque<Integer> dq;
    public MaxQueue() {
    
        this.q = new LinkedList<>();
        this.dq = new LinkedList<>();
    }
    
    public int max_value() {
    
        return this.dq.isEmpty() ? -1 : this.dq.peek();
    }
    
    public void push_back(int value) {
    
        this.q.add(value);
        // 单调队列 非严格递减，保留相等的副本。
        while(!this.dq.isEmpty() && value > this.dq.peekLast()){
    
            dq.pollLast();
        }
        this.dq.add(value); // 添加元素
    }
    
    public int pop_front() {
    
        if(this.q.isEmpty()) return -1;
        int x = this.q.poll();
        if(x == this.dq.peek()) this.dq.pop(); // 通过值的判断
        return x;
    }
}
// 数组模拟
class MaxQueue {
    
    int[] q = new int[10000];
    int[] dq = new int[10000];
    int i = 0, j = 0, left = 0, top = 0;

    public MaxQueue() {
     }
    
    public int max_value() {
    
        return i == j ? -1 : this.dq[left];
    }
    
    public void push_back(int value) {
    
        q[j++] = value;
        // 单调队列 非严格递减，保留相等的副本。
        while(left <= top && value > dq[top]){
    
            top --;
        }
        this.dq[++top] = value;
    }

    public int pop_front() {
    
        if(i == j) return -1;
        int x = q[i++];
        if(x == dq[left]) left++; // 通过值的判断
        return x;
    }
}