LeetCode 735. 小行星碰撞
目录
题目描述
题意分析
数组
asteroids从左到右描述同一行上的一排小行星：正数表示向右飞，负数表示向左飞，绝对值表示体积。要求返回所有碰撞结束后剩下的小行星，仍按原来的左右顺序排列。碰撞规则是「体积小的爆炸，体积相等的同归于尽，同向飞行的永远不会相遇」。这里有一个必须先想清楚的约束信号：两颗小行星要相遇，必须是左边那颗向右飞、右边那颗向左飞。也就是说，只有「正数在左、负数在右」这一种组合会碰撞。正数在右、负数在左是背向远离；两个都是正数或者都是负数是同速同向，永远追不上。
因此整道题的动作只有一种：一颗向左飞的小行星，去撞它左边那些向右飞的小行星。撞击是连锁的——撞碎一颗之后，它可能继续往左撞下一颗。
需要照顾的边界包括：体积相等时两颗都消失；一颗负数连续撞碎多颗正数；全部同向时一颗都不会消失；所有小行星互相抵消后结果为空数组。数据范围 $1 \le n \le 10^4$，
asteroids[i]非零且绝对值不超过 1000，所以取相反数不会溢出。
解法：栈模拟连续碰撞
核心思路
小行星按位置从左到右给出。只有一种方向组合会碰撞：左边的小行星向右（正数），右边的小行星向左（负数）。同向运动不会追上，左负右正则会彼此远离。
从左到右扫描，用栈保存处理完当前前缀后仍存活的小行星。新来的正数不会与左侧碰撞，直接入栈；新来的负数只可能先撞上栈顶的正数，因为栈顶是离它最近的存活小行星。
当「栈顶为正、当前值为负」时比较绝对大小：
- 栈顶较小：栈顶爆炸，当前小行星仍存活，继续和新的栈顶比较；
- 大小相等：两者都爆炸，弹栈并结束当前轮；
- 栈顶较大：当前小行星爆炸，栈不变。
循环不变量是：扫描完前
i个元素后，栈按原顺序保存这个前缀最终的幸存者，栈内不存在尚未处理的碰撞对。因此一颗负数只需反复检查栈顶，直到它爆炸、栈空，或栈顶不再是正数。
解题步骤
- 初始化空栈，依次读取每颗小行星
asteroid，先标记它仍存活。- 当当前值为负、栈顶为正且当前仍存活时，进入碰撞循环。
- 栈顶更小时弹栈并继续；相等时弹栈且让当前值消失；栈顶更大时只让当前值消失。
- 碰撞循环结束后，若当前值仍存活，就把它压栈。
- 扫描完成后，栈中元素就是最终结果，顺序无需反转。
例如
[10, 2, -5]：10、2先入栈；-5撞碎2后还要继续，与10比较时自身爆炸，最终得到[10]。这也说明碰撞判断必须是循环，不能只写一次if。
代码实现
import java.util.Arrays;
class Solution {
public int[] asteroidCollision(int[] asteroids) {
int[] stack = new int[asteroids.length];
int size = 0;
for (int asteroid : asteroids) {
boolean alive = true;
while (alive && asteroid < 0 && size > 0 && stack[size - 1] > 0) {
int top = stack[size - 1];
if (top < -asteroid) {
size--;
} else if (top == -asteroid) {
size--;
alive = false;
} else {
alive = false;
}
}
if (alive) {
stack[size++] = asteroid;
}
}
return Arrays.copyOf(stack, size);
}
}
func asteroidCollision(asteroids []int) []int {
stack := make([]int, 0, len(asteroids))
for _, asteroid := range asteroids {
alive := true
for alive && asteroid < 0 && len(stack) > 0 && stack[len(stack)-1] > 0 {
top := stack[len(stack)-1]
if top < -asteroid {
stack = stack[:len(stack)-1]
} else if top == -asteroid {
stack = stack[:len(stack)-1]
alive = false
} else {
alive = false
}
}
if alive {
stack = append(stack, asteroid)
}
}
return stack
}
复杂度分析
- 时间复杂度：$O(n)$。虽然有嵌套循环，但每颗小行星最多入栈一次、出栈一次，所有弹栈操作合计不超过
n次。- 空间复杂度：$O(n)$。最坏情况下没有碰撞，栈保存全部小行星。
关键点总结
- 是否碰撞取决于相邻幸存者的方向：只有「正数在左、负数在右」需要处理。
- 当前负数可能连续撞碎多个较小的正数，因此必须使用
while。- 三种大小关系要完整区分；相等时双方都消失。
- 栈始终保存已处理前缀的最终幸存者，返回时保持原顺序，不需要反转。
- 面试解释复杂度时要用摊还分析：内层循环每继续一次就永久弹出一个元素，所以整体不是 $O(n^2)$。
易错点总结
- 把碰撞循环写成
if：[10, 2, -5]会错误保留-5，正确答案是[10]。- 相等时只删除一方：
[8, -8]应同时消失，结果为空。- 漏掉方向条件：
[-2, -1]同向向左，不能互相碰撞。- 栈顶较小时弹栈后立刻结束，会漏掉当前负数与更左侧正数的连续碰撞。
- 返回整个定长数组而不是有效前缀，会把未使用位置的 0 一并返回；Java 需截取到
size。- 对最终栈再做反转会破坏原有位置顺序，栈底到栈顶本来就是从左到右。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 20. 有效的括号 | 简单 | 栈做括号配对消除 |
| 71. 简化路径 | 中等 | 栈做路径分段规约 |
| 739. 每日温度 | 中等 | 单调栈求右侧第一个更大元素 |
| 946. 验证栈序列 | 中等 | 模拟压入弹出序列的合法性 |
| 1047. 删除字符串中的所有相邻重复项 | 简单 | 相邻同值元素成对消除 |
| LCR 037. 行星碰撞 | 中等 | 本题的同题异名版本 |