Asteroid Collision
一排小行星沿着一条直线飞行，速度都相同。asteroids 中的每个值都表示一颗小行星：它的绝对值表示大小，正负号表示方向，正数表示向右，负数表示向左。
向右移动的小行星遇到向左移动的小行星时，它们会相撞。较小的那颗会爆炸；如果它们一样大，两颗都会爆炸。向同一方向移动的小行星永远不会相遇。请按原来的顺序返回所有碰撞后剩下的小行星。结果可能为空。
函数
- asteroidsinteger-array
- 从左到右依次表示小行星、方向符号、大小的绝对值
- 返回值integer-array
- 由左到右排列的幸存小行星，可能一个也没有
约束条件
1 ≤ asteroids.length ≤ 104-1000 ≤ asteroids[i] ≤ 1000asteroids[i] ≠ 0
示例
- 输入
- asteroids = [4, 9, -6, 2, -3]
- 输出
- [4, 9]
- 解释
- 9 遇到 -6 并获胜。2 遇到 -3 后爆炸，然后 -3 继续飞向 9，也爆炸了。没有其他东西朝任何目标移动，所以剩下 4 和 9。
- 输入
- asteroids = [6, -6]
- 输出
- []
- 解释
- 6 和 -6 以相同的大小崩溃，所以它们都会爆炸，结果为空。
- 输入
- asteroids = [-2, -7, 3, 8]
- 输出
- [-2, -7, 3, 8]
- 解释
- -2 和 -7 向左飞，3 和 8 向右飞，因此两组彼此远离。它们永远不会相撞，四颗小行星都能存活下来。
进阶
栈可以判断哪些小行星会存活。你还要如何报告每颗爆炸的小行星是被哪颗小行星摧毁的，并给出摧毁它的小行星的索引？
提示
逐个打开提示，每个都会多透露一点。
发生碰撞需要左侧有向右移动的小行星，右侧有向左移动的小行星。向左移动的小行星前方没有向右移动的小行星，就永远不会发生碰撞。从左向右遍历这一行：一个新的向左移动的小行星仍然可能撞上哪些更早出现的小行星？
新出现的左移者会先撞上最近的幸存右移者，然后撞上下一个，依此类推，直到它爆炸或没有右移者为止。目前的幸存者表现得像一个栈：只有最新的幸存者会成为下一个被撞上的对象。
将幸存者保存在栈中。将每个向右移动的物体压入栈中。遇到向左移动的物体时，如果栈顶是较小的向右移动物体，就将它弹出。如果栈顶是大小相同的向右移动物体，就将它弹出，并丢弃新物体。如果栈顶更大，就丢弃新物体。否则，将新物体压入栈中。
题解
一个向左移动的小行星可以摧毁一长串向右移动的小行星，每次碰撞都可能暴露出一对新的小行星，让它们接着碰撞。新出现的小行星总是先遇到最近的幸存者，因此用栈保存幸存者，就能在一次遍历中解决所有碰撞。
一次解决一个崩溃
结果正确，但无法在最大的测试中运行完毕
思路
当一颗向右移动的小行星紧挨着一颗向左移动的小行星，且位于它的左侧时，两颗小行星就会相撞。找到最先出现的这对小行星，处理它们，然后从左侧重新扫描。当不再有这样的配对时，就不会再发生碰撞，这一行就是答案。
处理顺序并不重要：两颗相邻且相向而行的小行星，会在任意一颗与其他小行星相撞之前先彼此相撞。
每次碰撞都需要重新扫描，并从这一行的中间移除一颗小行星。9,999 颗向右移动的小型小行星后面跟着 -1000 时，每次扫描都会遍历这一行并摧毁一颗向右移动的小行星：大约需要 5 × 10^7 步。
算法
- 复制这一行，这样你就可以从中移除小行星。
- 从左向右扫描，找到第一个满足
i且row[i] > 0和row[i+1] < 0的索引。 - 如果没有这样的索引，就返回这一行。
- 否则，移除两个小行星中较小的一个；如果它们大小相等，则同时移除，然后再次扫描。
def asteroidCollision(asteroids):
row = list(asteroids)
while True:
# A crash happens where a right-mover is directly followed by a left-mover.
hit = -1
for i in range(len(row) - 1):
if row[i] > 0 and row[i + 1] < 0:
hit = i
break
if hit == -1:
return row
right, left = row[hit], -row[hit + 1]
if right > left:
del row[hit + 1]
elif right < left:
del row[hit]
else:
del row[hit:hit + 2]幸存者堆栈
思路
把目前幸存的天体保存在栈中。栈中不会出现右向移动的天体后面跟着左向移动的天体的情况，因为这对天体早已相撞，所以栈中先是一些逃脱的左向移动天体，后面跟着右向移动天体。
新的右向移动天体会飞离栈中的所有天体，因此将它压入栈中。新的左向移动天体会朝栈顶的右向移动天体飞去，并且先遇到最新的一个，所以栈顶是它接下来唯一可能撞上的小行星。在第一个示例中，-3 弹出 2，然后与 9 相撞并爆炸，栈 [4, 9] 按原顺序排列就是答案。
每颗小行星最多入栈一次、出栈一次，因此即使一颗左向移动的小行星清除了一长串小行星，这一趟遍历的时间复杂度仍是 O(n)。
算法
- 从一个空的幸存者栈开始。
- 对于每颗小行星，如果它向右移动，就将它压入栈中并继续。
- 如果它向左移动，就从栈顶弹出比它小的向右移动的小行星。
- 如果此时栈顶是大小相同、向右移动的小行星，就将它弹出，并移除这颗新小行星。如果栈顶是更大的向右移动的小行星，就移除这颗新小行星。否则，将它压入栈中。
- 从栈底到栈顶返回这个栈。
def asteroidCollision(asteroids):
survivors = [] # the row so far, after every crash it caused
for rock in asteroids:
alive = True
# Only a left-mover can hit something: a right-mover on top of the stack.
while alive and rock < 0 and survivors and survivors[-1] > 0:
top = survivors[-1]
if top < -rock:
survivors.pop() # the right-mover is smaller and explodes
elif top == -rock:
survivors.pop() # same size: both explode
alive = False
else:
alive = False # the right-mover is bigger: the new one explodes
if alive:
survivors.append(rock)
return survivors
易错点和边界情况
- 把左移者后面跟着右移者的情况当成碰撞。在
[-2, -7, 3, 8]中，两组会彼此飞离，四个移动者都会存活。 - 弹出元素时使用
if而不是while。在[1, 2, 3, 4, 5, -15]中，左移者会摧毁所有五个右移者并存活。 - 漏掉相等的情况。
[6, -6]必须弹出 6 并丢弃 -6，结果为空。 - 把已经失败的左移者压入栈中。在
[9, -6]中，-6 会爆炸，不能放到栈上。用一个标志记录它是否仍然存活。
常见问题3
小行星碰撞的时间复杂度是多少？
时间复杂度为 O(n)，使用幸存者栈时，空间复杂度为 O(n)，因为每颗小行星最多入栈和出栈一次。每次碰撞后重新扫描这一行，时间复杂度为 O(n²)。
为什么栈是解决小行星碰撞问题的合适数据结构？
一颗新小行星只能到达离它最近的幸存者，并且会从最新的幸存者开始接触，再到最早的幸存者。这就是后进先出。最后仍在栈上的幸存者不会再发生碰撞，因此他们就是最后一行。
Asteroid Collision 可以用 O(1) 的额外空间解决吗？
可以，前提是你可以覆盖输入。把数组的开头用作栈：保留一个写入索引 top，与 asteroids[top-1] 比较，并返回前 top 个元素。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def asteroidCollision(asteroids):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
asteroids = [4, 9, -6, 2, -3]
预期输出
[4, 9]