735. 小行星碰撞 Medium

给定一个整数数组 asteroids，表示在同一行的小行星。数组中小行星的索引表示它们在空间中的相对位置。

对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。

找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。

示例 1：
输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

示例 2：
输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。

示例 3：
输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。

解题思路

输入：一个整数数组 asteroids，每个元素表示一个行星的方向和大小（正数向右，负数向左）

输出：返回所有碰撞结束后仍存活的行星数组

本题是典型的 栈结构 + 邻项消除模拟 问题。

我们使用一个栈 stack 来模拟当前仍在飞行中的行星：

• 遍历数组中的每个行星；

• 如果当前行星向右（正数），或栈为空，或栈顶行星也向左（负数）→ 无冲突，直接入栈；

• 如果当前行星向左（负数），且栈顶行星向右（正数），则发生碰撞：

  • 若当前行星绝对值更大，栈顶行星被摧毁，当前行星继续与新的栈顶比较；
  • 若两者大小相等，双双销毁，当前行星不入栈；
  • 若栈顶行星更大，当前行星被摧毁，终止比较；

• 遍历结束后，栈中剩下的即为未被摧毁的行星。

代码实现

python

from typing import List

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []  # 用栈保存仍在运动中的小行星

        for asteroid in asteroids:
            # 标记当前小行星是否被摧毁
            alive = True

            # 如果当前小行星向左飞（负数），且栈顶小行星向右飞（正数），就可能发生碰撞
            while stack and asteroid < 0 < stack[-1]:
                if abs(asteroid) > stack[-1]:
                    # 当前小行星更大，栈顶小行星爆炸，继续比较下一个栈顶
                    stack.pop()
                elif abs(asteroid) == stack[-1]:
                    # 两者相同，双双爆炸
                    stack.pop()
                    alive = False
                    break
                else:
                    # 栈顶小行星更大，当前小行星爆炸
                    alive = False
                    break

            # 如果当前小行星还活着，则压入栈中
            if alive:
                stack.append(asteroid)

        return stack

javascript

/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
const asteroidCollision = function(asteroids) {
    const stack = [];

    for (let speed of asteroids) {
        let alive = true;

        while (stack.length && stack.at(-1) > 0 && speed < 0) {
            if (stack.at(-1) > Math.abs(speed)) {
                alive = false;
                break;
            } else if (stack.at(-1) < Math.abs(speed)) {
                stack.pop();
            } else {
                alive = false;
                stack.pop();
                break
            }
        }

        if (alive) stack.push(speed);
    }

    return stack;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

735 国际版

735 中文版