735. Asteroid Collision

LeetCode задача 735

Задача

Мы имеем массив asteroids целых чисел, представляющих астероиды в ряду. Для каждого астероида абсолютное значение представляет его размер, а знак представляет его направление (положительное означает вправо, отрицательное влево). Все астероиды движутся с одинаковой скоростью. Необходимо определить состояние астероидов после всех столкновений.

Подсказки

Для решения задачи можно использовать стек.

Подход

Мы будем использовать стек для отслеживания движущихся вправо астероидов. Когда мы видим астероид, движущийся влево, мы проверяем, будет ли он сталкиваться с верхним элементом стека (астероидом, движущимся вправо).

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

Алгоритм

1. Инициализируем пустой стек.
2. Проходимся по каждому астероиду:
   1. Если астероид движется вправо, просто добавляем его в стек.
   2. Если астероид движется влево:
      1. Сравниваем его с верхним элементом стека.
      2. Если верхний элемент меньше по абсолютному значению, удаляем его из стека.
      3. Если верхний элемент равен текущему астероиду по абсолютному значению, удаляем оба.
      4. Если верхний элемент больше текущего астероида по абсолютному значению, переходим к следующему астероиду
3. Возвращаем стек в качестве результата.

Решение

def asteroidCollision(asteroids):
    stack = []
    for asteroid in asteroids:
        # Если астероид движется вправо
        if asteroid > 0:
            stack.append(asteroid)
        else:
            # Пока в стеке есть астероиды, движущиеся вправо, и они меньше текущего астероида по абсолютному значению
            while stack and stack[-1] > 0 and stack[-1] < -asteroid:
                stack.pop()
            # Если стек пуст или верхний элемент стека движется влево
            if not stack or stack[-1] < 0:
                stack.append(asteroid)
            # Если верхний элемент стека равен текущему астероиду по абсолютному значению
            elif stack[-1] == -asteroid:
                stack.pop()
    return stack