Topic:

Define a queue and implement the max_value function to get the maximum value in the queue, requiring the amortized time complexity of max_value, push_back, and pop_front to be O(1).

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

Answer key:

class MaxQueue {
    Queue<Integer> q;
    Deque<Integer> d;

    public MaxQueue() {
        q = new LinkedList<Integer>();
        d = new LinkedList<Integer>();
    }
    
    public int max_value() {
        if (d.isEmpty()) {
            return -1;
        }
        return d.peekFirst();
    }
    
    public void push_back(int value) {
        while (!d.isEmpty() && d.peekLast() < value) {
            d.pollLast();
        }
        d.offerLast(value);
        q.offer(value);
    }
    
    public int pop_front() {
        if (q.isEmpty()) {
            return -1;
        }
        int ans = q.poll();
        if (ans == d.peekFirst()) {
            d.pollFirst();
        }
        return ans;
    }
}
Copy the code

Answer:

This algorithm is based on an important property of the problem: when an element is queued, all elements smaller than it in front of it no longer affect the answer. For example, if we insert a sequence of numbers 1, 1, 1, 1, 2 into the queue, then after the first number 2 is inserted, all 1’s before the number 2 will have no effect on the result. Because of the queue fetch order, the number 2 can only be retrieved after all the number 1 has been retrieved, so if the number 1 is in the queue, then the number 2 must also be in the queue, so that the number 1 has no effect on the result.

Following the above thread, we can design such a method that when we insert an element from the end of the queue, we can pre-fetch all the elements in the queue that are smaller than this element, so that only the numbers that affect the result remain in the queue. Such an approach is equivalent to maintaining a monotonic decrement of the queue, that is, ensuring that each element is preceded by no smaller element.

So how do you efficiently implement a consistently decreasing queue? We just need to insert each element value, from the end of the queue, the element value is smaller than the current element value, until the element value’ is larger than the current element. The above procedure ensures that as long as the queue is decayed before the element value is inserted, it is still decayed after the value is inserted. The initial state of the queue (empty queue) meets the definition of monotonically decreasing. By mathematical induction we know that the queue will always be monotonically decreasing. The above procedure requires fetching elements from the tail of the queue, so it needs to be implemented using a double-endided queue. We also need a secondary queue to record all inserted values to determine the return value of pop_front. After the monotonic decrement of the queue is guaranteed, the maximum value can be obtained only by taking the first item in the double-ended queue directly.

To understand:

Make sure that the order of the secondary queue is decremented from front to back, so that the first element in each queue is the largest element, and when you want to fetch the first element, you can do this by inserting an element from the back of the queue, As long as there are elements smaller than that in front of you, remove them using removeRear(), the deque’s method of removing elements from the end of the queue. A deque is a two-endian queue, as described in the previous article.