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

题目

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 特别注意如果用Java做本题要熟悉Deque和Queue的API，对于Deque来说，能当队列也能当栈，本题会当队列来用，所以查看尾部元素应该用PeekLast()，而不是Peek()，因为Peek()相当于PeekFirst()
• 额外维护一个保存最大值的双向队列，从队头到队尾，应该是逆序的，即当队尾元素小于当前要进队的元素时，要while弹出去这些小元素，从而保证是逆序的
• 出栈的时候，只需要判断一下两个队列的队头是否相等，相等则把这个逆序双向队列也弹出。

Java AC

class MaxQueue {
    
    private Queue<Integer> q = new LinkedList<>();
    private Deque<Integer> dq = new LinkedList<>();

    public MaxQueue() {
    

    }
    
    public int max_value() {
    
        if(q.isEmpty()){
    
            return -1;
        }
        return dq.peekFirst();
    }
    
    public void push_back(int value) {
    
        q.add(value);
        while(!dq.isEmpty()&& dq.peekLast()<value){
    
            dq.removeLast();
        }
        dq.add(value);
    }
    
    public int pop_front() {
    
        if(q.isEmpty()){
    
            return -1;
        }
        int res = q.poll();
        if(dq.peekFirst()==res){
    
            dq.removeFirst();
        }
        return res;
    }
}

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