Trexquant OA 面试真题解析：Asteroid Collision（数组栈模拟碰撞）

We are given an array asteroids of integers representing asteroids in a row. The indices of the asteroids in the array represent their relative position in space.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide, resulting in 10. The 5 and 10 never collide.

这道题本质上是用栈模拟相向运动的碰撞过程：数组中正数表示向右、负数表示向左，只有当栈顶是向右移动的正数且当前元素是向左移动的负数时，才可能发生碰撞。每次比较两者绝对值，较小者被消除；如果相等则同时消失；如果栈顶更大，则当前行星继续与前一个栈元素比较。这样可以在一次遍历中完成所有碰撞，时间复杂度为 O(n)，适合在线面试中考察栈的应用和条件模拟能力。