首页 > 其他 > 详细

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

时间:2021-03-27 22:33:39      阅读:21      评论:0      收藏:0      [点我收藏+]

和上一道题差不多的思想,利用辅助双端队列队首存储最值。

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

class MaxQueue {

    Deque<Integer> A;
    Deque<Integer> B;
    public MaxQueue() {
        A = new LinkedList<>();
        B = new LinkedList<>();
    }
    
    public int max_value() {
        return B.isEmpty() ? -1 : B.peekFirst();
    }
    
    //A维护正常队列,B队首存储最值
    public void push_back(int value) {
        A.offerLast(value);
        //将双向队列中队尾 所有 小于 value 的元素弹出(以保持 deque 非单调递减)
        while(!B.isEmpty() && B.peekLast() < value)
            B.pollLast();
        B.offerLast(value);
    }
    
    public int pop_front() {
        if(A.isEmpty())
            return -1;
        //若A首元素和B首元素 相等 ,则将B首元素出队
        if(A.peekFirst().equals(B.peekFirst()))
            B.pollFirst();
        return A.pollFirst();
    }
}

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

 

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

原文:https://www.cnblogs.com/deerlet/p/14586457.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!