LeetCode LCR 037. 行星碰撞
目录
题目描述
题意分析
数组中每个元素表示一颗行星：绝对值是大小，正负号是方向（正数向右、负数向左），所有行星速度相同。相向而行的两颗会相撞，小的爆炸；大小相等则同归于尽；同向或背向的永远不会相撞。求最终稳定下来的数组。
「速度相同」这个条件极其关键：它意味着同向的两颗行星永远追不上对方，同时也意味着相对位置不变，谁在左谁就永远在左。所以碰撞只可能发生在一种组合上——左边的正数遇上右边的负数。左边负数、右边正数是背向而行，永不相遇。
由此，每读到一颗向左飞的行星，它只会与它左侧那些仍然存活且向右飞的行星依次相撞，且是从最近的一颗开始撞起。「最近的先处理、撞掉了再看更远的」正是后进先出的访问顺序。
碰撞的结果有三种，必须逐一想清楚：右飞的更大，则左飞的爆炸，右飞的原地不动；两者相等，则双双爆炸；左飞的更大，则右飞的爆炸，左飞的继续往左撞下一颗。第三种情形会连锁反应，所以需要一个循环而不是一次判断。
边界：全是正数或全是负数时不会有任何碰撞；负数在前正数在后（如
[-2, 1]）也不会碰撞；最终结果可能为空数组。数值方面题目保证元素不为 0，所以不用担心「大小为 0」的退化情形。
解法：模拟过程
核心思路
暴力做法是反复扫描数组，每轮找出一对相撞的行星并删除，直到没有可撞的为止。一次删除是 $O(n)$ 的搬移，轮数也可能是 $O(n)$，整体退化到 $O(n^2)$，而且「删完之后新暴露出来的一对又要重新扫」这种反复回退非常难写对。
瓶颈在于「删除之后要回头看」。观察这个回退方向：删掉一颗右飞行星后，需要重新检查的是它左边的那一颗。也就是说，所有回退都朝同一个方向、且总是从最近的元素开始——这正是栈的语义，把「回头看」变成「弹栈」。
于是状态定义为：栈里自底向上保存的是已扫描部分中最终存活下来的行星，且它们的相对顺序就是最终答案的顺序。这个不变量比「栈里是候选」更强，正因为它成立，扫描结束时把栈从底到顶取出就直接是答案。
扫描规则按当前行星的方向分两支。
遇到正数：它向右飞，绝不会与栈里任何元素相撞（栈里的正数在它左边同向，栈里的负数在它左边背向），直接入栈。
遇到负数
x（记它的大小为-x）：它要与栈顶依次结算。先用一个循环处理「栈顶是正数且比它小」的情形——这些右飞行星逐个被撞碎，弹栈继续。循环退出后有三种可能：栈顶是正数且大小恰好相等，那么两者同归于尽，弹掉栈顶且当前行星也不入栈；栈为空或栈顶是负数（同向），说明当前行星一路畅通，入栈；剩下的情形只能是栈顶是更大的正数，当前行星被撞碎，什么都不做。三个分支的顺序必须是「先循环弹小的，再判等，再判可入栈」，因为它们对栈顶的要求依次收紧，颠倒会漏掉情形。
解题步骤
- 准备栈：Java 用
ArrayDeque并统一以尾部为栈顶（offerLast入栈、pollLast出栈、peekLast看栈顶），这样最后用stream()从头到尾输出就天然是从栈底到栈顶的正确顺序；Go 直接用切片，尾部即栈顶。- 正数直接入栈：
if (x > 0) stk.offerLast(x);。向右飞的行星与左侧任何存活行星都不可能相遇，无需任何判断。- 负数先撞碎所有更小的右飞行星：
while (!stk.isEmpty() && stk.peekLast() > 0 && stk.peekLast() < -x) stk.pollLast();。三个条件缺一不可——栈非空防越界，栈顶为正才可能相撞，栈顶更小才会被撞碎。这个循环实现了连锁反应。- 判断同归于尽：
if (!stk.isEmpty() && stk.peekLast() == -x) stk.pollLast();。大小相等时两颗都消失，所以弹掉栈顶后不要把当前行星入栈。- 判断畅通入栈：
else if (stk.isEmpty() || stk.peekLast() < 0) stk.offerLast(x);。栈空说明左边已无阻挡，栈顶为负说明同向不会相撞，两种情形当前行星都存活。- 其余情形什么都不做：能落到这里只剩「栈顶是更大的正数」，当前行星被撞碎，直接丢弃。
- 输出栈内元素：从栈底到栈顶即为答案顺序。
以
asteroids = [5, 10, -5]走一遍。5是正数入栈，栈为[5]；10是正数入栈，栈为[5, 10]；-5是负数，先看循环条件：栈顶10为正但10 < 5不成立，循环不执行；再判等：10 == 5不成立；再判畅通：栈非空且栈顶为正，不成立。三支都没命中，说明-5被10撞碎，直接丢弃。最终栈为[5, 10]，正确。再看连锁反应的用例
[10, 2, -5]：10入栈得[10]，2入栈得[10, 2]。处理-5：循环第一轮栈顶2为正且2 < 5，弹出得[10]；第二轮栈顶10为正但10 < 5不成立，循环结束。判等10 == 5不成立；判畅通不成立。于是-5被10撞碎。最终[10]，正确——如果没有那个while循环而只判断一次，2撞碎后就不会再与10结算，会错误地把-5留下。再看同归于尽的用例
[8, -8]：8入栈得[8]；处理-8：循环条件8 < 8不成立；判等8 == 8成立，弹出栈顶得[]，且当前行星也不入栈。最终为空数组，正确。最后看永不碰撞的用例
[-2, -1, 1, 2]：-2是负数，栈空，循环与判等都不成立，命中「栈为空」这一支入栈；-1同样是负数，栈顶-2为负，循环与判等都不成立，命中「栈顶为负」这一支入栈；1与2都是正数直接入栈。最终[-2, -1, 1, 2]原样输出，正确。
代码实现
class Solution {
public int[] asteroidCollision(int[] asteroids) {
// 栈里自底向上是已扫描部分最终存活的行星，顺序即答案顺序。
Deque<Integer> stk = new ArrayDeque<>();
for (int x : asteroids) {
if (x > 0) {
// 向右飞，与左侧任何存活行星都不会相遇。
stk.offerLast(x);
} else {
// 连锁撞碎所有更小的右飞行星。
while (!stk.isEmpty() && stk.peekLast() > 0 && stk.peekLast() < -x) {
stk.pollLast();
}
if (!stk.isEmpty() && stk.peekLast() == -x) {
// 大小相等，同归于尽，当前行星也不入栈。
stk.pollLast();
} else if (stk.isEmpty() || stk.peekLast() < 0) {
// 左边已无阻挡，或栈顶同向，当前行星存活。
stk.offerLast(x);
}
// 其余情形：栈顶是更大的正数，当前行星被撞碎，直接丢弃。
}
}
return stk.stream().mapToInt(Integer::valueOf).toArray();
}
}
func asteroidCollision(asteroids []int) (stk []int) {
// 栈里自底向上是已扫描部分最终存活的行星，顺序即答案顺序。
for _, x := range asteroids {
if x > 0 {
// 向右飞，与左侧任何存活行星都不会相遇。
stk = append(stk, x)
} else {
// 连锁撞碎所有更小的右飞行星。
for len(stk) > 0 && stk[len(stk)-1] > 0 && stk[len(stk)-1] < -x {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 && stk[len(stk)-1] == -x {
// 大小相等，同归于尽，当前行星也不入栈。
stk = stk[:len(stk)-1]
} else if len(stk) == 0 || stk[len(stk)-1] < 0 {
// 左边已无阻挡，或栈顶同向，当前行星存活。
stk = append(stk, x)
}
// 其余情形：栈顶是更大的正数，当前行星被撞碎，直接丢弃。
}
}
return
}
复杂度分析
- 时间复杂度：$O(n)$。每颗行星至多入栈一次、出栈一次，
while循环的总弹栈次数被入栈总数限制住，因此虽然嵌套了循环，整体仍是线性的均摊代价；构造返回数组再扫一遍栈也是 $O(n)$。- 空间复杂度：$O(n)$，栈的最大深度出现在没有任何碰撞时（如全为正数），此时所有行星都留在栈里。返回值数组不计入额外空间。
关键点总结
- 先把「什么情况下会发生碰撞」推清楚——只有「左正右负」这一种，这一步就把问题从二维的两两比较压成一次线性扫描。
- 「删除后需要回头看最近的元素」是选择栈最典型的信号，它把 $O(n^2)$ 的反复回退变成均摊 $O(n)$ 的弹栈。
- 让栈的不变量直接就是「最终存活者」而不是「候选者」，扫描结束就不需要任何后处理，输出即答案。
- 三个分支的判定顺序按「对栈顶的要求由松到紧」排列：先循环弹掉更小的、再判相等、再判可入栈，颠倒任何一步都会漏情形。
- 连锁反应必须用循环而不是单次判断，一次碰撞可能暴露出新的对手，这是本题与普通单调栈最像的地方。
- 面试视角：面试官常追问「为什么保证是 $O(n)$ 而不是 $O(n^2)$」，标准回答是每个元素最多入栈出栈各一次的均摊分析；再追问「如果速度不同呢」，那就不再是相邻结算，需要按到达时间排序或用其他模型，能指出这条边界说明你真正理解了「速度相同」这个前提的作用。
易错点总结
- 连锁碰撞只判一次不用循环：
[10, 2, -5]中2被撞碎后不再与10结算，会错误输出[10, -5]，正确答案是[10]。- 同归于尽时把当前行星也入栈：
[8, -8]会输出[-8]，而正确答案是空数组。while条件漏掉stk.peekLast() > 0：[-2, -1]处理-1时会把同向的-2误当作对手弹出，输出[-1]而不是[-2, -1]。while条件用<=而不是<：大小相等的情形会在循环里被弹掉，然后当前行星又满足「栈空」而入栈，[8, -8]会输出[-8]。- 忘记判空就取栈顶：
[-5]这种以负数开头的输入，第一轮就对空栈调用peekLast并参与比较，直接崩溃或读到空值。- 正数也去和栈顶结算：
[-2, 3]里3会与背向的-2错误相撞，输出被清空，而正确答案是原样保留。- 用
-x之外的写法比较大小：直接拿x（负数）与栈顶比较，[5, -10]中5 < -10恒不成立，-10撞不掉5，输出错误。- 输出顺序反了：把栈从顶到底弹出拼接，
[5, 10]会输出[10, 5]；用ArrayDeque时要确认入栈方向与遍历方向一致。- 在原数组上原地删除元素：每次删除都要搬移后续元素，
[1, 2, 3, ..., -n]这类用例会退化成 $O(n^2)$ 并超时。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 735. 小行星碰撞 | 中等 | 与本题同题，可直接套用单栈模拟 |
| 20. 有效的括号 | 简单 | 同样是「与最近的元素结算」，但结算规则是配对而非比较大小 |
| 844. 比较含退格的字符串 | 简单 | 退格符消费栈顶字符，是「遇到标记就弹栈」的最简形态 |
| 1046. 最后一块石头的重量 | 简单 | 同样是两两对撞剩余差值，但每次挑的是最大的两块，需要用堆而非栈 |
| 946. 验证栈序列 | 中等 | 用栈模拟压入弹出过程，考察的是能否复现给定的操作序列 |
| 1381. 设计一个支持增量操作的栈 | 中等 | 在栈的基础上加区间增量，练的是把额外状态挂在栈元素上的技巧 |