jz59_2.队列的最大值

题目描述

题解

辅助队列

在第三十题中使用辅助栈的方法完成了最小值的功能, 这道题沿用该辅助结构的思想, 为队列创建一个辅助队列, 每当往主队列中执行入队和出队操作时都要考虑维护辅助栈.

当入队时, 为了保证辅助队列的单调性, 需要先将所有比该数小的元素删除

出队的如果正是辅助队列的最大元素, 那么要将该元素从辅助队列中删除

class MaxQueue {

    Deque<Integer> deque1;
    Deque<Integer> deque2;

    public MaxQueue() {
        deque1 = new LinkedList<>();
        deque2 = new LinkedList<>();
    }

    public int max_value() {
        if (deque2.isEmpty()) {
            return -1;
        }
        return deque2.peekFirst();
    }

    public void push_back(int value) {
        deque1.add(value);
        while (!deque2.isEmpty() && deque2.peekLast() < value) {
            deque2.pollLast();
        }
        deque2.add(value);

    }

    public int pop_front() {
        if (deque1.isEmpty()){
            return -1;
        }
        if (!deque2.isEmpty()&&deque1.peekFirst().equals(deque2.peekFirst())){
            deque2.pollFirst();
        }
        return deque1.pollFirst();
    }
}