Монотонный стек

Стек, из которого вовремя удаляют лишнее

Монотонный стек — это обычный стек, в котором элементы поддерживаются в возрастающем или убывающем порядке. Перед добавлением нового значения с вершины удаляются элементы, которые больше не могут быть полезны для ответа. Так стек хранит не всю историю, а только актуальных кандидатов.

Пример: следующий больший элемент

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

static int[] nextGreater(int[] numbers) {
    int[] result = new int[numbers.length];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < numbers.length; i++) {
        while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
            int index = stack.pop();
            result[index] = numbers[i];
        }
        stack.push(i);
    }

    return result;
}

Почему это O(n), хотя есть вложенный while

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

Ключевой вопрос при таком подходе: когда кандидат становится бесполезным навсегда? Если на него можно ответить локальным сравнением с новым элементом, монотонный стек часто позволяет убрать повторные просмотры массива.