Стек с максимумом (Max Stack)

Условие:

Реализуйте стек целочисленных значений с методами:

• push(value) — добавить значение в стек.

• pop() — удалить верхний элемент стека и вернуть его.

• max() — вернуть максимальное значение в стеке.

Все методы должны работать за O(1).

Если вызывается pop() или max() для пустого стека, нужно вернуть null.

Входные данные:

Последовательность операций со стеком.

Каждая операция имеет вид:

["push", value]
["pop"]
["max"]

Выходные данные:

Массив результатов для операций pop и max.

Операция push ничего не возвращает.

Ограничения:

1 <= operations.length <= 100000
-10^9 <= value <= 10^9

Пример:

Вход:

[
  ["push", 1],
  ["push", 3],
  ["push", 7],
  ["push", 1],
  ["max"],
  ["pop"],
  ["max"],
  ["pop"],
  ["max"]
]

Выход:

[7, 1, 7, 7, 3]