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

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

就是题目 剑指 Offer 59 - I. 滑动窗口的最大值 需要实现的数据结构。

一个队列用于正常加入和删除数据，另一个队列用于维护最大值。

class MaxQueue {
    Deque<Integer> q = new ArrayDeque<>();
    Deque<Integer> q_max = new ArrayDeque<>();

    public MaxQueue() {

    }
    
    public int max_value() {
        if(q.isEmpty()) return -1;
        return q_max.peekFirst();
    }
    
    public void push_back(int value) {
        q.offerLast(value);
        while(!q_max.isEmpty() && q_max.peekLast() < value){
            q_max.pollLast();
        }
        q_max.offerLast(value);     
    }
    
    public int pop_front() {
        if(q.isEmpty()) return -1;
        int pop = q.pollFirst();
        if(pop == q_max.peekFirst()){
            q_max.pollFirst();
        }
        return pop;
    }
}