Комментарии 23
Хорошо бы было еще и объяснение почему алгоритм со стеком для ближайшего слева работает. Так было бы понятнее. Ключевая идея в том, что вот рассморим текущий элемент. Может ли он быть ближайшим слева большим для каких-то элементов? Если следующий справа его больше - то уже точно нет. Потому что этот справа и ближе ко всем остальным элементам и больше данного.
Поэтому, если мы начнем рассматривать все потенциальные ближайшие слева в текущем начале массива, то заметим, что они образуют возрастающую последовательность справа-налево. Потому что если бы там было убывание, то меньший никогда бы не мог быть ответом для кого-то другого. А дальше надо посмотреть, как меняются кандидаты при добавлении в рассмотрение следующего числа.
Ещё можно добавить, что, несмотря на вложенный цикл, там O(n) по времени, потому что во вложенном цикле делается снятие со стека, а каждый элемент добавится в стек один раз, итого суммарно n внутренних итераций.
Объяснение принципа работы... Представьте стопку тарелок...
Команду "top()" так мысленно и не представил с тарелками :)))
Спасибо за статью!
ИМХО стек это не структура данных, а некий намеренно ограниченный по операциям интерфейс взаимодействия со структурой данных
С какой структурой данных? Это вопрос, т.к. стек можно реализовать и на базе массива, и на связном списке, на каких-то промежуточных типа deque, ...
Это конечно дискуссионный вопрос, тут смотря как трактовать термины. Но если бы мне предложили выбрать из предложенных элементов, то что меньше всего относится к структурам данных:
массив,
связный список,
хэш-таблица,
стек,
ассоциативный массив на красно-черном дереве
То это был бы стек
а некий намеренно ограниченный по операциям интерфейс взаимодействия со структурой данных
Такой термин уже существует, и называется абстрактный тип данных, сокращенно АТД. Там и стек, и очередь, и ассоциативный массив, и многие другие.
Для задачи со скобками стек не нужен, достаточно счетчика. Начинаем счетчик с нуля, и по очереди перебираем символы, если символ открытой скобки - добавляем единицу к счетчику. Если символ закрытой скобки - проверяем, если счетчик, если он больше нуля, то вычитаем единицу и идем дальше. А если счетчик равен 0, значит закрывать нечего, последовательность неправильная, завершаем проверку.
Это работает только в случае, когда скобки одного типа (например, только круглые). В случае 3 типов - не работает. ({)} - контрпример
Да, точно, не обратил внимание, что скобки могут быть разных типов. Поспешишь - людей насмешишь. :)
А если использовать 3 счётчика?
Только что хотел написать про скобки(что разные типы не работают), но тут уже в комментарии все написали про это🥲
В любом случаи спасибо тебе за статью!
В решение задачи со скобками можно ещё добавить проверку длины последовательности на нечётность.
Хорошо бы было еще и объяснение почему алгоритм со стеком для ближайшего слева работает. Так было бы понятнее. Ключевая идея в том, что вот рассморим текущий элемент. Может ли он быть ближайшим слева большим для каких-то элементов? Если следующий справа его больше - то уже точно нет. Потому что этот справа и ближе ко всем остальным элементам и больше данного.
Поэтому, если мы начнем рассматривать все потенциальные ближайшие слева в текущем начале массива, то заметим, что они образуют возрастающую последовательность справа-налево. Потому что если бы там было убывание, то меньший никогда бы не мог быть ответом для кого-то другого. А дальше надо посмотреть, как меняются кандидаты при добавлении в рассмотрение следующего числа.
Я решил эту задачку со всероса, но я использовал дп, а потом оптимизировал его не тривиальным способом через стек как раз. А тут очень лаконичное решение, всё гениальное - просто
Вот они, олимпиадники… Код корректный, но ужасный, отвратительный.
Столько таких повидал за время работы, для меня «Призер олимпиады» - красный флаг.
Только детям мозги ломаете :( На 1000 олимпиадников находится только 1, которому это пошло на пользу.
Очень простая структура данных, с помощью которой решаются сложные задачи