剑指 Offer 59 - II. 队列的最大值 (opens new window)

1.单调队列

具体分析见[][239.滑动窗口最大值 | Blage's Coding (blagecode.cn)]239.滑动窗口最大值 | Blage's Coding (blagecode.cn) (opens new window)

class MaxQueue {
    Deque<Integer> q1;
    Deque<Integer> q2;
    public MaxQueue() {
        q1=new LinkedList<>();
        q2=new LinkedList<>();
    }
    
    public int max_value() {
        if(q2.size()==0) return -1;
        return q2.peekFirst();
    }
    
    public void push_back(int value) {
        q1.offerLast(value);
        while(q2.size()>0&&q2.peekLast()<value)q2.pollLast();
        q2.offerLast(value);

    }
    public int pop_front() {
        if(q1.size()==0) return -1;
        int del=q1.peekFirst();
        q1.pollFirst();
        if(q2.peekFirst()==del) q2.pollFirst();
        return del;
    }
}