Привет, друзья. Помните задачку на валидацию скобочной последовательности? Она считается очень легкой и на leetcode она в разряде easy задач. Я же никогда не считал, что ее по сложности можно сравнить с каким-нибудь слиянием отсортированных массивов. Львиная доля ее легкости заключается в мейнстримности этой задачи - едва ли не каждый знает каноническое решение через стек. А между тем, это далеко не единственная задача, которую можно оптимально решить через эту структуру данных. И, если попросить кандидата решить немного другую задачу с похожей идеей решения, то вполне можно вогнать человека в ступор :). Как всегда, дело в умении распознать класс задачи, а вот применить паттерн решения уже не составляет труда.
Поэтому, сегодня мы разберем задачу о столкновении астероидов.
P.S. Если быть честным, у меня ушло около 40 минут на реализацию и отладку решения через 2 индекса, прежде чем я догадался воспользоваться стеком. Решение через стек вышло сильно лаконичнее и быстрее в реализации 🙂
Сложность: 🟠 Средняя
ℹ️ Описание
Напишите функцию, которая будет рассчитывать результаты столкновения астероидов.
Входные данные: массив целых ненулевых чисел. Каждое число обозначает массу астероида, знак - направление движения.
Выходные данные: массив целых ненулевых чисел. Массив будет описывать множество астероидов, их массу и направление, после того, как все астероиды, которые могут столкнуться, столкнутся.
Все астероиды движутся с одинаковой скоростью. Таким образом, астероиды, летящие в одном направлении никогда не столкнутся друг с другом.
В отличие от реальной жизни, при столкновении масса и направление движение астероидов после никак не изменяются. Меньший из двух полностью уничтожается, больший продолжает лететь в прежнем направлении, не меняя массу.
⚠️ Ограничения
- Количество астероидов (длина входного массива) находится в диапазоне от 2 до 10000
- Масса астероида лежит в диапазоне от 1 до 1000 (знак влияет только на направление движения)
- Астероидов с нулевой массой не существует
1️⃣Пример
Входящие данные
[]int{5,10,-5}
Ответ
[]int{5,10}
Пояснение
Первые два астероида движутся вправо, последний - влево. В результате, второй и третий астероид должны столкнуться. Второй астероид имеет большую массу, поэтому он полностью уничтожит третий.
2️⃣ Пример
Входящие данные
[]int{8,-8}
Ответ
[]int{}
Пояснение
Астероиды движутся навстречу друг другу и имеют одинаковую массу. В результате оба астероида будут уничтожены.
3️⃣ Пример
Входящие данные
[]int{10,2,-5}
Ответ
[]int{10}
Пояснение
Первые два астероида движутся вправо, последний - влево. В результате, третий астероид уничтожит второй. и продолжит движение влево. После этого столкнуться первый и третий астероиды, а так как первый имеет большую массу, он уничтожит третий.
✅ Решение
Посмотреть подробное объяснение решения
#stack #medium