Design

Abstract：leetcode Design专题题解

面试题59 - II. 队列的最大值

解法一：辅助队列

和minStack有点像，当然minStack可以不需要不需要辅助栈，是因为先进后出的特性

• 辅助队列如何记录最大值？
  • 队首维护最大值
  • 对于新加入的value，从队尾找起，如果队列中存在比value小的，统统删掉，因为它们不会影响最大值的结果

完整实现

class MaxQueue {

    private LinkedList<Integer> q;
    private LinkedList<Integer> helper;

    public MaxQueue() {
        q=new LinkedList<>();
        helper=new LinkedList<>();
    }
    
    public int max_value() {
        if(helper.size()!=0)return helper.getFirst();
        return -1;
    }
    
    public void push_back(int value) {
        while(helper.size()!=0 && value>helper.getLast())
            helper.removeLast();                     //从队尾找起，小于value的统统删掉
        q.add(value);
        helper.add(value);
    }
    
    public int pop_front() {
        if(q.size()!=0){
            int e=q.removeFirst();
            if(e==helper.getFirst())               //如果pop的是最大值，则同步一下helper
                helper.removeFirst();
            return e;
        }
        return -1;
    }
}

/**
 * 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();
 */