Min Stack

Средняя№155значение + минимум

Нужно написать стек с push, pop и top, который ещё отвечает getMin — наименьшее значение в нём, и каждый вызов должен работать за O(1). pop, top и getMin вызывают только у непустого стека. Наш пример: push(5), push(3), push(7), push(3), getMin(), pop(), getMin(), pop(), pop(), getMin(), top(). Четыре ответа: 3, 3, 5 и 5.

155 Min StackРазбор · 1×

Пример: push(5), push(3), push(7), push(3), getMin(), pop(), getMin(), pop(), pop(), getMin(), top(). Каждый столбец — одна запись: сверху значение, под ним low — минимум этой записи и всех под ней.

вызовMinStack()valuelow—ответы—
в стекетолько что положили; low, который читает pushубрали через popчто возвращает вызов

Создаём MinStack(): init выполняется один раз

01/35
сначала · назад · пуск · шаг
Скорость
1class MinStack:
2 function init():
3 stack = empty stack of pairs (value, low)
4 function push(x):
5 low = x
6 if stack is not empty:
7 low = min(x, stack.last.low)
8 push (x, low) onto stack
9 function pop():
10 remove stack.last
11 function top():
12 return stack.last.value
13 function getMin():
14 return stack.last.low
состояние
stack
–
x
–
low
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Пока запись лежит в стеке, всё под ней не меняется: измениться оно может только после того, как её снимут. Поэтому low, записанный при push, верен, пока запись в стеке.
  2. low новой записи — меньшее из её значения и low под ней, поэтому getMin — это low верхней записи: одно обращение.
  3. pop уносит свой low, а запись ниже уже хранит минимум без неё. Поэтому одной переменной для минимума мало, а повторяющийся минимум не нужно считать.

Сложность

Время O(1) на каждый вызов: он читает или меняет только верх. Память O(n) на n записей, по два числа в каждой.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.