Монотонная очередь

Кандидаты для текущего окна

Монотонная очередь обычно хранится в deque и поддерживает кандидатов в отсортированном по значению порядке. Новые элементы добавляются с одного конца, а бесполезные удаляются с другого. В отличие от обычной очереди, часть элементов может исчезнуть ещё до того, как дошла бы до головы: если новый кандидат гарантированно лучше старого.

Максимум в каждом окне

Пусть для каждого окна длины k нужен максимум. В deque будем хранить индексы так, чтобы соответствующие значения шли по убыванию. Голова тогда всегда указывает на максимум текущего окна.

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;
}

Два разных повода удалить элемент

Индекс удаляется с головы, когда он вышел за левую границу окна. С хвоста элементы удаляются по другой причине: новое значение не меньше их, поэтому пока оно остаётся в окне, старые кандидаты уже не смогут стать максимумом.

Каждый индекс добавляется и удаляется не более одного раза, поэтому обработка всех окон занимает O(n), а deque использует до O(k) памяти.