Легкий

Проблема

Разработайте стек, который поддерживает push, pop, top и извлечение минимального элемента за постоянное время.

  • push(x) — Поместить элемент x в стек.
  • pop() — удаляет элемент с вершины стека.
  • top() — Получить верхний элемент.
  • getMin() — Получить минимальный элемент в стеке.

Пример:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Решение

Это легко, если мы просто хотим реализовать структуру данных, поддерживающую эти операции. Однако было бы интересно, если бы мы хотели, чтобы все операции выполнялись за время O(1). Если мы хотим это сделать, мы должны использовать другой стек, скажем, минимальный стек, для сохранения минимального значения для соответствующей позиции в исходном стеке.

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

С помощью вышеописанных операций можно легко обнаружить, что всякий раз, когда элемент был отправлен или вытолкнут, минимальный стек сохранит текущее минимальное значение всего стека данных в своей верхней позиции. Поэтому выполнить операцию getMin всегда можно за O(1).

Сложность

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