Столкновения астероидов (стековый подход)

Допустим, у нас есть такая проблема:

Нам дан массив asteroids целых чисел, представляющих астероиды подряд.

Для каждого астероида абсолютное значение представляет его размер, а знак представляет его направление (положительное значение означает право, отрицательное значение означает лево). Каждый астероид движется с одинаковой скоростью.

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

Для начала можно представить пример:

Значения представляют размер астероида, а атрибут -/+ представляет направление (отрицательные значения перемещаются влево, а положительные значения перемещаются вправо). .

Если мы проиллюстрируем серию происходящих столкновений, это будет выглядеть примерно так:

Мы начнем со всех наших астероидов до того, как они столкнутся.

Затем астероид со значением +10 сталкивается с меньшим астероидом -5 и уничтожает его.

Затем астероид со значением +10 сталкивается с более крупным астероидом -15 и впоследствии удаляется.

Наконец, астероиды со значением +5 и -15 сталкиваются, при этом -15 уничтожает меньший астероид. У нас остался ответ [-15].

Решение

Во-первых, давайте посмотрим на код, прежде чем объяснять его.

public int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();

    for(int i=0; i<asteroids.length; i++) {
        int asteroid = asteroids[i];
        if(!stack.isEmpty() && stack.peek() > 0 && asteroid < 0) {

            // Equal (Both asteroids get destroyed)
            if(Math.abs(asteroid) == Math.abs(stack.peek())) {
                stack.pop();
            }

            // Current asteroid is bigger than one at top of stack
            // Top asteroid in stack gets destroyed
            // Re-check current asteroid with next in stack
            else if(Math.abs(asteroid) > Math.abs(stack.peek())) {
                stack.pop();
                i--;
            }
        }
        else {
            // No collision, add asteroid to stack
            stack.push(asteroid);
        }
    }


    // Build a new array (backwards stack)
    int[] res = new int[stack.size()];
    for(int i=stack.size()-1; i>=0; i--) {
        res[i] = stack.pop();
    }

    return res;
}

Объяснение

Сначала мы начинаем с [5, 10, -5, -15] в нашем массиве астероидов.

Мы просматриваем массив и добавляем элементы в стек, если они соответствуют любому из следующих требований:

Стек пуст
Верхний элемент (астероид) в стопке перемещается влево.
Астероид движется вправо

Мы сразу видим, что первые два астероида в массиве будут помещены в стек. Во время первой итерации стек пуст, поэтому мы добавляем в стек [5].

Во второй итерации астероид движется вправо, поэтому мы добавляем в стек 10. [5, 10]

Третья итерация, когда астероид -5 не соответствует этим условиям. У нас есть текущий астероид, движущийся влево, а последний астероид в стопке двигался вправо. Нас ждет столкновение!

Поскольку астероиды -5 и 10 не эквивалентны, а текущий астероид -5 не больше предыдущего астероид в стопке, мы ничего не делаем. Мы не добавляем -5 в стек, так как он будет уничтожен.

Затем мы переходим к последнему астероиду в массиве, то есть -15. Еще раз: текущий астероид (-15) движется влево, а последний астероид (10) движется вправо, поэтому мы входим в первое условие if.

Мы видим, что текущий астероид (-15) больше, чем последний астероид в группе (10), поэтому столкновение уничтожит последний астероид в стопке. Мы извлекаем 10 из стека. Мы также должны быть уверены, что не повторяем i, поскольку нам нужно продолжать проверять следующие столкновения -15. .

Аналогичным образом мы проверяем -15 против 5, и происходит то же самое. 5 удаляется из стека. iне увеличивается.

На последней итерации стек пуст, поэтому мы добавляем в стек -15.

Мы возвращаем инверсию стека.

Пожалуйста, обратите внимание на следующую анимацию.

Анимация

Анализ производительности:

Сложность времени:

Цикл проходит по каждому астероиду один раз (O(n)), где n — количество астероидов.
Внутри цикла операции стека (push, pop, peek) имеют среднюю временную сложность O(1), поскольку стеки обычно реализуются как динамические массивы или связанные списки.
Цикл повторно посещает индекс только тогда, когда текущий астероид больше, чем астероид в верхней части стека, и в этом случае индекс i уменьшается. В большинстве случаев это позволяет избежать ненужных операций.

В целом временная сложность вашего алгоритма равна O(n), где n — количество астероидов.

Космическая сложность:

Стек используется для хранения астероидов, которые еще не столкнулись. В худшем случае все астероиды могут оказаться в стопке, если не столкнутся.
Следовательно, пространственная сложность алгоритма также равна O(n), где n — количество астероидов.