Условие задачи

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

Необходимо реализовать класс MinStack со следующими методами:

• MinStack() - конструктор класса;
• void push(int val) - добавляет элемент val на вершину стека;
• void pop() - удаляет элемент, находящийся на вершине стека;
• int top() - возвращает верхний элемент стека;
• int getMin() - возвращает минимальный элемент стека.

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

Пояснения и примеры

• Метод push(int val) добавляет элемент val на вершину стека.
  • Пример:
    • Стек до добавления: [3, 5, 2, 7]
    • push(1)
    • Стек после добавления: [1, 3, 5, 2, 7]
• Метод pop() удаляет элемент на вершине стека.
  • Пример:
    • Стек до удаления: [1, 3, 5, 2, 7]
    • pop()
    • Стек после удаления: [3, 5, 2, 7]
• Метод top() возвращает элемент, находящийся на вершине стека.
  • Пример:
    • Стек: [3, 5, 2, 7]
    • top() вернет 3
• Метод getMin() возвращает минимальный элемент стека.
  • Пример:
    • Стек: [3, 5, 2, 7]
    • getMin() вернет 2

Решение

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

• Основной стек будет хранить все элементы стека;
• Вспомогательный стек будет хранить минимальные значения элементов основного стека на каждой позиции (т.е. на каждой позиции вспомогательного стека будет храниться минимальный элемент основного стека, который находится на этой же позиции).

Пример:

• Основной стек: [3, 5, 2, 7]