Leetcode sword finger offer 59 - ii Maximum value of queue

subject

Please define a queue and implement the function max_value Get the maximum in the queue , Function required max_value、push_back and pop_front The average time complexity of is O(1).

If the queue is empty ,pop_front and max_value Need to return -1

Example 1：

 Input : 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
 Output : [null,null,null,2,1,2]

Example 2：

 Input : 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
 Output : [null,-1,-1]

Limit ：

1 <= push_back,pop_front,max_value Total number of operations for  <= 10000
1 <= value <= 10^5

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas

• Pay special attention if Java Be familiar with this topic Deque and Queue Of API, about Deque Come on , It can be a queue or a stack , This topic will be used as a queue , So to view the tail element, you should use PeekLast(), instead of Peek(), because Peek() amount to PeekFirst()
• Maintain an additional two-way queue that holds the maximum value , From head to tail , It should be in reverse order , That is, when the element at the end of the team is smaller than the element currently entering the team , want while Pop up these small elements , So as to ensure that it is in reverse order
• When you push the stack , Just judge whether the heads of the two queues are equal , If it is equal, the reverse two-way queue will also pop up .

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