Почему это работает
- Пока запись лежит в стеке, всё под ней не меняется: измениться оно может только после того, как её снимут. Поэтому low, записанный при push, верен, пока запись в стеке.
- low новой записи — меньшее из её значения и low под ней, поэтому getMin — это low верхней записи: одно обращение.
- pop уносит свой low, а запись ниже уже хранит минимум без неё. Поэтому одной переменной для минимума мало, а повторяющийся минимум не нужно считать.
Сложность
Время O(1) на каждый вызов: он читает или меняет только верх. Память O(n) на n записей, по два числа в каждой.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗