Реализуйте в Java класс, представляющий стек (stack), который поддерживает операции push, pop и получение минимального элемента (getMin) — все операции должны выполняться за константное время (O(1)). Напишите код и объясните, как вы решите эту задачу.
Объяснение:
В этом коде используется два стека:
stack для хранения элементов стека и minStack для хранения минимальных элементов.В методе
push, при добавлении нового элемента в стек проверяется, является ли он минимальным. Если да, то он также добавляется в minStack.В методе
pop, при извлечении элемента из стека проверяется, является ли этот элемент минимальным. Если да, то он также удаляется из minStack.Методы
top и getMin просто возвращают верхний элемент стека и минимальный элемент соответственно.Сложность:
Временная сложность для всех операций: O(1). Все операции выполняются за константное время, так как мы используем два стека и не производим поиск по всему стеку для поиска минимального элемента.
Пространственная сложность: O(n). Где n — количество элементов в стеке. Мы используем два стека, но их размер ограничен размером стека.