Сложность: hard
Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.
Пример:
Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]
👨💻 Алгоритм:
1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов.
2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.
3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.
😎 Решение:
class MaxStack:
def __init__(self):
self.stack = []
self.max_stack = []
def push(self, x):
self.stack.append(x)
if not self.max_stack or x >= self.max_stack[-1]:
self.max_stack.append(x)
def pop(self):
x = self.stack.pop()
if x == self.max_stack[-1]:
self.max_stack.pop()
return x
def top(self):
return self.stack[-1]
def peekMax(self):
return self.max_stack[-1]
def popMax(self):
max_val = self.max_stack.pop()
buffer = []
while self.stack[-1] != max_val:
buffer.append(self.stack.pop())
self.stack.pop()
while buffer:
self.push(buffer.pop())
return max_val
Ставь 👍 и забирай 📚 Базу знаний