Interview Question 59: Maximum Queue

1. Title Description

Problem (1) Maximum value of sliding window
Given an array and the size of a sliding window, find the maximum value in all sliding windows.
For example, if the input array {2, 3, 4, 4, 2, 2, 6, 2, 2, 2, 2, 2, 2, 5, 1}, and the size 3 of the slider window, then there are six slider windows, {[2,3,4], 2,6,6,6,2,2,2,2,5,1}, {2,3,[3,4,2], 6,2,2,5,5,1}, {2,3,3,1},{2,3,3,4,4,2,{2,3,2,3,4,2,[6,3,4,2,2,[6,3,4,4,2,[6,2,2,2,2,2,2,2,2,5,5,4,4,4 4,2,6, [2,5,1]}.Their maximum values are {4, 4, 6, 6, 5}

Question (2) Maximum Queue
Define a queue and implement the function max to get the maximum value in the queue, requiring that the time complexity of the functions max, push_back, and pop_front are all O(1).

2. Problem Analysis

Problem (1) Analysis
The most direct method is violence: the maximum value is found by comparing each sliding window in turn, but the time complexity is high and the answer is unsatisfactory.

Consider recording each number that may become the maximum so that you can get the maximum quickly.

We set up a queue with openings at both ends to place all possible maximum numbers (corresponding subscripts) at the beginning of the queue.

Scan the array from scratch:

• If the number you encounter is larger than all the numbers in the queue, then it is the maximum value. Other numbers cannot be the maximum value. Empty all the numbers in the queue and place them at the top of the queue.
• If the number encountered is smaller than all the numbers in the queue, it may also become the maximum value of the sliding window at the end of the queue.
• If you encounter a number that is smaller than the maximum and larger than the minimum in the queue, it is impossible for a smaller number to become the maximum. Delete the smaller number and place it in the queue.
• Because of the size of the sliding window, the number of the queue head is also deleted if its subscript is greater than the window size from the end of the sliding window.

Java has built-in double-ended queues.ArrayDeque

Question (2)
Once the above problem has been solved, it is much simpler, as well as using a two-end queue to store the maximum values in the current queue and the possible maximum values in the future.

When defining a queue for title-requirement functionality, in addition to defining a queue data to store numeric values, an additional queue maxmium is needed to store the maximum possible values; in addition, a data structure is defined to store data and the current index value to determine whether the maximum value in maxmium is deleted during deletion operations.

3. Question Answers

Question (1)

    public ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> max = new ArrayList<Integer>();
        if(num==null || num.length<=0 || size<=0 || size>num.length) {
            return max;
        }

        ArrayDeque<Integer> indexDeque = new ArrayDeque<>();

        for(int i=0;i<size-1;i++){
            while(!indexDeque.isEmpty() && num[i]> num[indexDeque.getLast()]) {
                indexDeque.removeLast();
            }
            indexDeque.addLast(i);
        }

        for(int i=size-1;i<num.length;i++){
            while(!indexDeque.isEmpty() && num[i]> num[indexDeque.getLast()]) {
                indexDeque.removeLast();
            }
            if(!indexDeque.isEmpty() && (i-indexDeque.getFirst())>=size) {
                indexDeque.removeFirst();
            }
            indexDeque.addLast(i);
            max.add(num[indexDeque.getFirst()]);
        }
        return max;
    }

Question (2)

    // Store data
    private ArrayDeque<InternalData>  data = new ArrayDeque<>();
    // Maximum Value
    private ArrayDeque<InternalData> maximum = new ArrayDeque<>();

    private class InternalData{
        int number;
        int index;
        public InternalData(int number,int index) {
            this.number=number;
            this.index=index;
        }
    }

    private int curIndex;

    public void push_back(int number) {
        InternalData curData = new InternalData(number,curIndex);
        data.addLast(curData);

        while(!maximum.isEmpty() && maximum.getLast().number < number) {
            maximum.removeLast();
        }
        maximum.addLast(curData);
        curIndex++;
    }

    public void pop_front() {
        if(data.isEmpty()) {
            System.out.println("The queue is empty and cannot be deleted!");
            return;
        }
        
        InternalData curData = data.removeFirst();
        if(curData.index==maximum.getFirst().index) {
            maximum.removeFirst();
        }
    }

    public int max() {
        if(maximum==null){
            System.out.println("The queue is empty and cannot be deleted!");
            return 0;
        }
        return maximum.getFirst().number;
    }