What is the key idea behind the Asteroid Collision problem?

The core concept is using a stack to track right-moving asteroids and resolving collisions immediately when left-moving asteroids appear.

Can two asteroids moving in the same direction collide?

No, asteroids moving in the same direction never collide, so the stack only stores right-moving asteroids for collision checks.

How does the stack ensure O(n) performance?

Each asteroid is pushed and popped at most once from the stack, ensuring linear time complexity without repeated scanning.

What happens when two asteroids are the same size?

Both asteroids explode and are removed from consideration, which must be checked when popping the stack.

How should I handle consecutive collisions in this problem?

Iteratively compare the current left-moving asteroid with the stack top, popping smaller asteroids until it either explodes or no collision remains.

#735

Medium

auto_awesome栈·状态

LeetCode 题解工作台

小行星碰撞

给定一个整数数组 asteroids ，表示在同一行的小行星。数组中小行星的索引表示它们在空间中的相对位置。对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。找出碰撞后剩下的所有小行星。碰撞规则：两个小行星…

数组栈模拟

题目描述

给定一个整数数组 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 。

示例 4：

输入：asteroids = [3,5,-6,2,-1,4]
输出：[-6,2,4]
解释：小行星 -6 使小行星 3 和 5 爆炸，然后继续向左移动。在另一边，小行星 2 使小行星 -1 爆炸，然后继续向右移动，没有碰撞小行星 4。

提示：

2 <= asteroids.length <= 10⁴
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

lightbulb

解题思路

方法一：栈

我们从左到右遍历每个小行星 $x$ ，由于每个小行星可能与之前的多个小行星发生碰撞，考虑用栈来存储。

对于当前小行星，如果 $x \gt 0$ ，那么它一定不会跟前面的小行星发生碰撞，我们可以直接将 $x$ 入栈。
否则，如果栈不为空并且栈顶元素大于 $0$ ，且栈顶元素小于 $-x$ ，那么栈顶元素对应的小行星会发生爆炸，我们循环将栈顶元素出栈，直到不满足条件。此时如果栈顶元素等于 $-x$ ，那么两个小行星会发生爆炸，只需要将栈顶元素出栈即可；如果栈为空，或者栈顶元素小于 $0$ ，那么当前小行星不会发生碰撞，我们将 $x$ 入栈。

最后我们返回栈中的元素即为答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $asteroids$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stk = []
        for x in asteroids:
            if x > 0:
                stk.append(x)
            else:
                while stk and stk[-1] > 0 and stk[-1] < -x:
                    stk.pop()
                if stk and stk[-1] == -x:
                    stk.pop()
                elif not stk or stk[-1] < 0:
                    stk.append(x)
        return stk

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask how to handle collisions without scanning the entire array repeatedly.
question_mark
Probe whether the candidate correctly uses the stack to track right-moving asteroids.
question_mark
Check if the candidate considers the edge case of equal-size collisions.

warning

常见陷阱

外企场景

error
Not handling multiple consecutive collisions for a single left-moving asteroid.
error
Confusing the order of collision resolution, leading to incorrect surviving asteroids.
error
Ignoring the sign and assuming all asteroids move toward each other.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow asteroids with varying speeds and require collision time computation.
arrow_right_alt
Track positions over time and return the sequence of collisions instead of final state.
arrow_right_alt
Extend to 2D grid where asteroids move in four directions and collide accordingly.

help

常见问题

外企场景

继续练习

#682 棒球比赛 #946 验证栈序列 #1441 用栈操作构建数组