Как стать автором
Обновить

Комментарии 13

НЛО прилетело и опубликовало эту надпись здесь
Копипаста проросла, поправил :)
Очередь — это структура данных с доступом к элементам LIFO (англ. Last In, First Out – «последним пришёл — первым ушёл»)

Эмм… Может очередь это FIFO?
Благодарю за замечание, опечатался)
Исправил)

Спасибо, "как" довольно очевидно (когда сообразишь, что наихудшее время O(1) не сделать, значит, ищем а ортизированное), а вот "зачем" – в голову не приходило.


К бонусной задачке: есть другой алгоритм поиска бегущего максимума/минимума за O(N), основанный на разбиении на отрезки по M чисел. Интересно, что придумали его только в 80-х.

Спасибо, что подсказали. Сразу начал гуглить и нашел статью на хабре на эту тему. Добавлю ссылку на нее тоже)

Есть еще другой алгоритм, без всяких предподсчетов и разбиений, но с одним деком.


Алгоритм не обобщается на любую ассоциативную операцию и работает только для min/max.


Структура поддерживает 3 операции — добавить в начало, убрать с конца и узнать максимум. Добавление амортизационно O(1), удаление и максимум — константны по времени.


Суть в том, что Вы должны держать список/дек элементов в окне, которые могли бы в какой-то момент стать максимумами. Они в окне будут образовывать убывающую последовательность. При добавлении в окно нового элемента, надо с конца выкинуть все элементы, меньше нового, чтобы последовательность осталась убывающей (они в окне уже никогда максимумом не будут, ведь они уйдут из окна раньше нового элемента, который уже больше). При удалении элемента из окна надо проверить, что элемент хранится в деке и удалить, если надо.

Хм… Разве это помогает получить min за О(1)?
То есть, для стека — да. Мы можем получить min за O(1), но разве это свойство сохранится, когда у нас будет очередь из двух стеков.

Берём минимум из двух минимумов же.

Очередь на двух стеках была в собеседовании на поступление в школу разработчиков hh
И еще, видимо, много где, так как попала даже в Cracking the Coding Interview
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.