题目重点：仅处理左侧向右和新来向左的相遇，覆盖相等抵消与多次碰撞。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练行星按位置顺序排列，速度绝对值相同；不支持零大小。
- 输出剩余有符号大小按原位置顺序；不存在距离或不同速度事件队列。
解题路线
- 栈保存已处理前缀最终幸存者。新行星只有负数且栈顶为正时会相撞；两个负数、两个正数、左负右正都不碰。
- 如果栈顶较小，弹出并继续与更早幸存者比较；相等弹栈且当前也死；栈顶较大仅当前死。循环结束当前仍活才push。
- 不变量：栈内无待发生的相向碰撞，且所有前缀事件已正确结算。新增项仅能与最右幸存者发生下一次碰撞，连续处理直到消失或没有相向邻居。
- 每个元素至多push一次pop一次，所以while累计线性，不能按每轮最坏n再乘外层n误判O(n²)。
手动走一遍
[10,2,-5]先消2再让-5消失，剩[10]；[8,-8]为空；[-2,-1,1,2]全部留下，虽符号混合却都远离。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def survivors(asteroids):
if any(value==0 for value in asteroids):
raise ValueError("zero size is undefined")
stack=[]
for current in asteroids:
alive=True
while alive and current < 0 and stack and stack[-1] > 0:
if stack[-1] < -current:
stack.pop()
elif stack[-1] == -current:
stack.pop()
alive=False
else:
alive=False
if alive: stack.append(current)
return stack
复杂度
O(n)时间、O(n)栈空间。
易错点与追问
容易失分的边界
- 正负符号不同就碰撞。
- 弹出一颗后未继续连锁。
- 相等只删一侧。
继续深挖
- 速度不同为何栈不够？
- 零大小如何定义而非默认？
- 如何同时返回幸存原下标？
