Алгоритм, реализующий стек со стандартными функциями push и pop и дополнительной функцией min за O(1)

Итак, оценка времени работы функция push, pop и min — O(1).

Экстремумы изменяются не часто. Фактически минимум может поменяться только при добавлении нового элемента.

Одно из решений — сравнивать добавляемые элементы с минимальным значением. Когда минимальное значение (minValue) удаляется из стека, приходится “перерывать” весь стек в поисках нового минимума. К сожалению, это нарушает ограничение на время выполнения О(1).

Если мы будем отслеживать минимум в каждом состоянии, то легко узнаем минимальный элемент. Можно, например, записывать для каждого узла текущий минимальный элемент, Затем, чтобы найти min, достаточно “вытолкнуть” вершину и посмотреть, какой элемент является минимальным.

Как только элемент помещается в стек, локальное значение минимума становится глобальным.

			public class StackWithMin extends Stack<NodeWithMin> {
    public void push(int value) {
        int newMin = Math.min(value,min());
        super.push(new NodeWithMin(value, newMin));
    }

    public int min() {
        if (this.isEmpty()) {
            return Integer.MAX_VALUE;
        } else {
            return peek().min;
          }
    }
}

class NodeWithMin {
    public int value;
    public int min;
    public NodeWithMin(int v, int min) {
        value = v;
        this.min = min;
    }
}
		

У решения один недостаток — если нужно обрабатывать огромный стек, то отслеживание минимального элемента потребует много ресурсов. Существует ли лучшее решение?

Оптимизировать код можно за счет использования дополнительного стека, который будет отслеживать минимумы.

			public class StackWithMin2 extends Stack<Integer> {
    Stack<Integer> s2;
    public StackWithMin2() {
        s2 = new Stack<Integer>();
    }

    public void push(int value) {
        if (value <= min()) {
            s2.push(value);
        }
        super.push(value);
    }

    public Integer pop() {
        int value = super.pop();
        if(value == min()) {
            s2.pop();
        }
        return value;
    }

    public int min() {
        if (s2.isEmpty()) {
            return Integer.MAX_VALUE;
        } else {
            return s2.peek();
          }
    }
}
		

Почему такое решение более эффективно? Предположим, что мы работаем с огромным стеком, первый вставленный элемент автоматически станет минимумом. В первом решение необходимо хранить n чисел, где n — размер стека. Во втором решении достаточно сохранить несколько фрагментов данных.

Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».