0735. Asteroid Collision

题目信息

题号:

0735

难度:

Medium

主题:

数组、碰撞模拟、栈

原题:

LeetCode 0735

重点:

下标表示初始相对位置,绝对值表示大小、符号表示方向;只有相向运动的天体可能碰撞,相等时双方消失,返回最终存活顺序

题目重述

给定整数数组 asteroids,表示一行天体。数组下标表示它们从左到右的初始相对位置;每个整数的绝对值表示天体大小,正数表示向右移动,负数表示向左移动。所有天体速度相同,数组中没有 0。

当天体相遇时,较小者爆炸;大小相等时双方都爆炸。一次碰撞后存活的天体可能继续与其他天体碰撞。同向运动的天体不会相遇,左侧向左与右侧向右的天体也会彼此远离。

返回所有碰撞结束后仍存活的天体,并保持它们从左到右的顺序。数组长度在 [2, 10^4] 范围内,-1000 <= asteroids[i] <= 1000 且 asteroids[i] != 0。

自建示例

连续碰撞后两侧天体远离:

输入:asteroids = [4,-2,-4,7,-9,3]
输出:[-9,3]
解释:4 先摧毁 -2,随后与大小相同的 -4 同时消失;7 被 -9 摧毁。最终 -9 向左、3 向右,二者彼此远离,不会碰撞。

没有天体会相遇:

输入:asteroids = [-3,-2,5,6]
输出:[-3,-2,5,6]
解释:左侧两个天体都向左移动,右侧两个天体都向右移动,任意一对都不会相向相遇,因此全部保留。