Максим Фатин | про IT

Опа! А вот и очередь на минимум подъехала

В общем, 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. сам пост отсылка на задачку Яндекса из будущего видоса на Ютубчике, так что ждите скоро большой видос про Яндекс

А 🌭 ускоряет выход видосов

🌭34❤‍🔥1

2.19K viewsedited 08:30