В общем, MinQueue поддерживает такие операции:
- вставка в конец (push) за O(1)
- удаление из начала (pop) за O(1)
- получить первый элемент (top) за O(1)
- получить минимальный (min) за O(1)
НО ЗАЧЕМ ВООБЩЕ ТАКОЕ НУЖНО?
На работе вряд ли встретится, а вот на собесе вполне (все из-за задачи про окно ограниченного размаха от Яндекса)
А ТЕПЕРЬ ДУШНОЕ ОБЪЯСНЕНИЕ
1) Есть стек (добавляет в конец и снимает с конца)
2) Есть стек на минимум (тот же стек, но за O(1) умеет минимум получать)
3) Есть очередь на двух стеках (обычная очередь)
А теперь если реализовать очередь на двух стеках на минимум, то получим MinQueue
Выглядеть это будет так:
class Stack:
def __init__(self):
self.stack = []
def __bool__(self):
return bool(self.stack)
def push(self, elem):
if self.stack:
self.stack.append(
(elem, min(elem, self.stack[-1][1]))
)
else:
self.stack.append((elem, elem))
def pop(self):
return self.stack.pop()[0]
def get_min(self):
if not self.stack:
return float("inf")
return self.stack[-1][1]
class MinQueue:
def __init__(self):
self.s1 = Stack()
self.s2 = Stack()
def push(self, elem):
self.s1.push(elem)
def pop(self):
if not self.s2:
while self.s1:
self.s2.push(self.s1.pop())
return self.s2.pop()
def get_min(self):
return min(
self.s1.get_min(),
self.s2.get_min()
)
Самое сложное: понять как работает черт побери эта очередь на двух стеках
По смыслу первый стек — сюда мы складываем новые элементы
А второй — отсюда забираем элементы в порядке очереди
Когда второй стек пустой, мы просто перекладываем в него все элементы из первого и тем самым переворачиваем их порядок
А минимум — это просто минимум из двух стеков
---
За более подробными объяснениями можно почитать ТУТ
P.S. сам пост отсылка на задачку Яндекса из будущего видоса на Ютубчике, так что ждите скоро большой видос про Яндекс
А 🌭 ускоряет выход видосов