剑指offer59-队列的最大值

原题(来源Leetcode)

请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_valuepush_backpop_front 的时间复杂度都是O(1)。

若队列为空,pop_frontmax_value 需要返回 -1

示例 1:

输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"] [[],[1],[2],[],[],[]] 输出: [null,null,null,2,1,2]

示例 2:

输入:
["MaxQueue","pop_front","max_value"] [[],[],[]] 输出: [null,-1,-1]

限制:

  • 1 <= push_back,pop_front,max_value的总操作数 <= 10000
  • 1 <= value <= 10^5

解法

思想

我一开始以为是要手写个堆。。。写完了之后发现自己理解错了题意 : )

就是另外使用一个双向队列维护一个单调递减的队列,如果要弹出的元素也是递减队列的头元素,就把它也弹出。

代码

class MaxQueue {
    Queue<Integer> queue = new LinkedList<>();
    Deque<Integer> deque = new LinkedList<>();
    public MaxQueue() {}

    public int max_value() {
        if(queue.size() == 0) return -1;
        return deque.peek();
    }

    public void push_back(int value) {
        queue.offer(value);
        while(deque.size()!=0&&deque.peekLast()<value){
            deque.pollLast();
        }
        deque.offer(value);
    }

    public int pop_front() {
        if(queue.size() == 0) return -1;
        int pop = queue.poll();
        if(pop == deque.peek()){
            deque.poll();
        }
        return pop;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer59-%e9%98%9f%e5%88%97%e7%9a%84%e6%9c%80%e5%a4%a7%e5%80%bc/