Monotonic Queue

Candidates for the current window

A monotonic queue is usually stored in a deque and keeps candidates ordered by value. New elements are added at one end, while useless ones are removed from the other. Unlike a regular queue, some elements can disappear before they would ever reach the head if a new candidate is guaranteed to be better.

Maximum in every window

Suppose we need the maximum for every window of length k. We will store indexes in the deque so that their corresponding values are in decreasing order. The head will then always point to the maximum of the current window.

static int[] maxInWindows(int[] numbers, int k) {
    int[] result = new int[numbers.length - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();

    for (int i = 0; i < numbers.length; i++) {
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.removeFirst();
        }
        while (!deque.isEmpty() && numbers[deque.peekLast()] <= numbers[i]) {
            deque.removeLast();
        }
        deque.addLast(i);

        if (i >= k - 1) {
            result[i - k + 1] = numbers[deque.peekFirst()];
        }
    }

    return result;
}

Two different reasons to remove an element

An index is removed from the head when it leaves the left boundary of the window. Elements are removed from the tail for another reason: the new value is not smaller than them, so while it remains in the window, those older candidates can no longer become the maximum.

Each index is added and removed at most once, so processing all windows takes O(n) time, while the deque uses up to O(k) memory.