行星碰撞 图解题解
这道题到底在问什么
- 输入
- [5,10,-5,-12]
- 输出
- [-12]
- 解读
- −5 被 10 撞爆;−12 连撞爆 10 和 5,自己活下来
最优解：一步一步想明白
- 3思路一句话：会撞的总是「在场的正数」和「刚来的负数」。用栈装活着的行星，负数来了和栈顶反复结算。下面一步步演给你看。
- 4栈空,从左往右读上面一排是输入流,我们从左往右一颗一颗读。下面的栈装「还活着的行星」,现在是空的。
- 5入栈 +5第一颗 +5 向右飞。正数永远不会和「它左边、同样向右」的撞,所以直接入栈等着。
- 6入栈 +10+10 也向右。和栈顶 +5 同向,撞不着,继续入栈。栈现在是 [+5, +10]。
- 7−5 vs +10:5 < 10 → −5 爆来了 −5(向左),栈顶 +10(向右)相向要撞:|−5|=5 < 10,−5 自己爆掉,+10 纹丝不动,−5 没能进栈。栈还是 [+5, +10]。
- 812 > 10 → +10 爆,弹栈最后一颗 −12 撞栈顶 +10:|−12|=12 > 10,+10 被撞爆弹出。但 −12 还活着,要继续面对新栈顶 +5!
- 912 > 5 → +5 爆,栈空新栈顶 +5,−12 接着撞:12 > 5,+5 也被撞爆弹出,栈空了。前面再没有挡路的正数——要不要继续撞?
- 10栈空,负数入栈栈空、没有正数挡在前面,−12 一路畅通入栈。读完了!最终栈 = [−12],就是答案。回看:−5 被秒、−12 连撞爆 10 和 5 后自己活下来。
- 11把这三种结局想清楚,这题的 while 就写对了。下面换几个小例子,专盯「等大同归于尽」「同向不撞」这两个边角。
- 12栈空,开读新例子 [8, −8],专看「等大同归于尽」。栈清空,从头读。
- 13入栈 +8先读 +8,正数入栈。
- 148 == 8 → 两颗都爆−8 撞栈顶 +8,大小完全相等。规则:一样大则两颗都爆——弹出 +8、−8 也不入栈,栈空,输出 []。这就是「相等」分支。
- 15栈空,开读再看 [10,2,−11],体会「负数弹完一个栈顶要继续撞下一个」的连环碰撞。栈清空,从头读。
- 16入栈 +10先 +10 入栈。
- 17入栈 +2+2 同向,入栈。栈 = [+10, +2]。
- 1811 > 2 → +2 爆,弹栈−11 撞栈顶 +2:11 > 2,+2 爆掉弹出。−11 还活着,继续撞新栈顶 +10。
- 1911 > 10 → +10 爆,栈空新栈顶 +10:11 > 10,+10 也被撞爆,栈空。−11 还活着,前面再没正数挡路。
- 20入栈 −11栈空、没有正数挡路,−11 入栈,输出 [−11]。一颗 −11 连弹了 +2、+10 才落地——这就是「弹完继续撞」。
- 21栈空,开读最后看 [−2,−1,1,2]:负数全在左、正数全在右,专看「背向不撞」。栈清空,从头读。
- 22入栈 −2读 −2,栈空没有正数挡路,直接入栈。
- 23入栈 −1−1 向左,栈顶 −2 也向左——同向,追不上,不撞,入栈。
- 24入栈 +1+1 向右。当前是正数,根本不进碰撞循环(只有「负数撞正栈顶」才撞),入栈。
- 25入栈 +2,无碰撞+2 入栈。整趟一次都没撞:左边的负数向左飞、右边的正数向右飞,背向越来越远。输出原样 [−2,−1,1,2]。
- 26把「唯一触发条件」记死:只有正数挡在左边、来个负数,才相向。其余都直接入栈。
- 30[8,−8] 错留 +8 ✗假如代码只处理「栈顶小才弹」,忘了「等大也要弹」:−8 撞 +8 时既没弹 +8、−8 又被标记为撞不动停下——结果错误地留下 +8。正确应输出 []。
⚠️ 容易写错的地方
✗ 错：无脑把每颗都先入栈再两两比
✓ 对：负数来时先和栈顶 while 结算,活下来才入栈
先入栈会让向左的负数被「同向」误判,逻辑全乱
✗ 错：碰撞循环里漏了「等大同归于尽」
✓ 对：栈顶 == |a| 时要弹栈顶,且当前也不入栈
漏了会让其中一颗错误存活(如 [8,−8] 错出 [8] 或 [−8])
✗ 错：弹出栈顶后忘了继续撞新栈顶
✓ 对：弹完 continue,让 −a 再战新栈顶
如 −12 撞爆 10 后还要撞 5,只撞一次会漏
完整代码（Python / C++ / Java）
Python
class Solution:
def asteroidCollision(self, asteroids):
stack = []
for a in asteroids:
alive = True
while alive and a < 0 and stack and stack[-1] > 0:
if stack[-1] < -a: # 栈顶小,弹出后继续撞
stack.pop()
continue
elif stack[-1] == -a: # 等大,两个都爆
stack.pop()
alive = False # 栈顶≥|a|: 当前爆掉,停
if alive:
stack.append(a)
return stackC++
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> stk;
for (int a : asteroids) {
bool alive = true;
while (alive && a < 0 && !stk.empty() && stk.back() > 0) {
if (stk.back() < -a) { stk.pop_back(); continue; }
if (stk.back() == -a) stk.pop_back();
alive = false;
}
if (alive) stk.push_back(a);
}
return stk;
}
};Java
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Deque<Integer> stack = new ArrayDeque<>();
for (int a : asteroids) {
boolean alive = true;
while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) {
if (stack.peek() < -a) { stack.pop(); continue; }
if (stack.peek() == -a) stack.pop();
alive = false;
}
if (alive) stack.push(a);
}
int[] res = new int[stack.size()];
for (int i = res.length - 1; i >= 0; i--) res[i] = stack.pop();
return res;
}
}复杂度
时间复杂度
O(n)
每颗行星最多入栈一次、出栈一次;while 里的每次弹出都对应一颗永久消失的行星,总弹出次数 ≤ n,故总操作线性。
空间复杂度
O(n)
最坏情况(全部同向、永不碰撞,如 [1,2,3] 或 [−1,−2,−3])栈里要装下所有 n 颗。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 行星碰撞 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么是 O(n) 而不是 O(n²)?+
while 看着像内层循环,但每次弹出都让一颗行星永久消失;每颗行星一生最多入栈一次、出栈一次,总操作数 ≤ 2n,所以线性。
为什么用栈而不是别的结构?+
新来的负数只会撞「离它最近的那颗在场正数」=栈顶,撞爆后又面对新栈顶,这种后进先出的就近结算天然契合栈。
怎么判断两颗会不会相撞?+
当且仅当左边那颗向右(正)、右边那颗向左(负)。同号、或左负右正(背离),都不会撞。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 行星碰撞 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。