企业官网建设流程全解析

• 教程
• 文档
• 知识库

导读：本文讲解 LeetCode 0735「小行星碰撞」题目的完整解法。这是一道典型的「栈 + 数组」模拟类中等题，核心在于利用栈的后进先出（LIFO）特性，模拟一排小行星同向运动时发生的连续碰撞。读完本文，你将掌握如何用单一栈在 O(n) 时间内完成「按方向成对消除」类问题的建模，并能举一反三地解决括号匹配、行星碰撞（LCR 037）等同族问题。

题目解读：同一行的小行星如何碰撞

题目大意

给定一个整数数组asteroids，表示在同一行运动的小行星：

• 每个元素的绝对值表示小行星的大小；
• 每个元素的正负号表示小行星的移动方向：正数向右移动，负数向左移动；
• 每一颗小行星以相同的速度移动。

碰撞规则只有三条：

• 两个行星相互碰撞时，较小的行星会爆炸消失；
• 如果两颗行星大小相同，则两颗都会爆炸消失；
• 两颗移动方向相同的行星，永远不会发生碰撞。

要求：找出碰撞后剩下的所有小行星，将答案存入数组并返回。

由于所有小行星速度相同、位于同一行，真正可能相遇的只有一种组合：向右移动的小行星（正数）在前，向左移动的小行星（负数）在后——即数组中「正数出现在负数左侧」时，两者必然相向而行并发生碰撞。

为什么用栈：碰撞只发生在「紧邻」的小行星之间

碰撞的天然特征是只发生在相邻（紧挨着）的相向小行星之间，而且一次碰撞后，幸存下来的小行星还会继续与更前面的小行星发生连锁碰撞。这种「后发生的碰撞取决于之前的结果、且总是从最近处开始」的过程，正是栈结构最擅长的场景：

• 栈顶始终是「当前最靠右、尚未被消灭」的小行星，也就是下一次碰撞的候选者；
• 出栈（pop）对应「小行星被撞爆炸」；
• 入栈（push）对应「小行星幸存并继续存在」。

这与 AlgoNote 算法通关手册中栈基础章节介绍的栈特性完全一致：栈只允许在栈顶进行插入和删除，遵循**后进先出（LIFO）**原则，非常适合处理「只关心最近一个元素、且需要回溯历史状态」的模拟问题。

解题思路：单栈模拟碰撞全过程

用栈模拟小行星碰撞，具体步骤如下：

1. 遍历数组asteroids，逐个处理小行星。
2. 入栈条件：如果栈为空，或者当前元素asteroid为正数（向右移动），直接将其压入栈。因为正数向右移动，不会与栈中左侧的任何行星相撞（左侧行星要么向左移动、要么同向右移动，均不会迎面相遇）。
3. 碰撞条件：如果当前栈不为空，且当前元素asteroid为负数（向左移动），说明它可能与栈中的行星相撞：
   • 连续碰撞：只要栈顶元素为正数，并且当前元素的绝对值大于栈顶元素（0 < stack[-1] < -asteroid），就把栈顶元素弹出——栈顶的右向小行星被撞爆炸，负向小行星继续前进，与新的栈顶继续碰撞。
   • 幸存入栈：碰撞结束后，如果栈为空，或者栈顶元素为负数（说明当前负向小行星一路撞穿了所有右向行星，或者原本左侧就没有右向行星），则将当前元素asteroid压入栈，表示碰撞后它幸存了下来。
   • 同归于尽：如果栈顶元素恰好与当前元素值大小相等、方向相反（stack[-1] == -asteroid），则弹出栈顶元素，表示碰撞后两者都爆炸了，当前负向小行星也不入栈。
4. 返回答案：遍历结束后，栈中剩下的元素就是所有碰撞后幸存的小行星，直接返回栈即可。

分步模拟示例

以asteroids = [5, 10, -5]为例：

结果为[5, 10]。

再看一个发生连锁碰撞的例子，asteroids = [10, 2, -5]：

结果为[10]，这里体现了「负向小行星撞穿一个正数后仍不敌更靠左的更大行星」的连续碰撞逻辑。

再验证「同归于尽」分支，asteroids = [8, -8]：

结果为[]。

代码实现

原文档给出的完整实现如下：

class Solution: def asteroidCollision(self, asteroids: List[int]) -> List[int]: stack = [] for asteroid in asteroids: if not stack or asteroid > 0: stack.append(asteroid) else: while stack and 0 < stack[-1] < -asteroid: stack.pop() if not stack or stack[-1] < 0: stack.append(asteroid) elif stack[-1] == -asteroid: stack.pop() return stack

关键代码逐行解读

• while stack and 0 < stack[-1] < -asteroid：这是整个算法的核心。0 < stack[-1]保证栈顶是向右移动的正数（只有正数才会与当前负数相撞）；stack[-1] < -asteroid等价于「栈顶大小 < 当前行星大小」，即当前负向小行星更大，撞毁栈顶后继续前进。
• 循环结束后有三种可能：
  • 栈为空或栈顶为负数 → 当前小行星幸存，stack.append(asteroid)；
  • 栈顶正数与当前行星大小相等 →stack.pop()，两者同归于尽；
  • 栈顶正数大于当前行星 → 当前行星被撞爆炸，不入栈也不弹栈。

复杂度分析

• 时间复杂度：O(n)。每个小行星最多入栈一次、出栈一次，虽然内层有while循环，但所有元素的总出栈次数不超过 n 次，因此整体仍是线性时间。
• 空间复杂度：O(n)。最坏情况下（如所有行星同向运动、互不碰撞）栈中需要保存全部 n 个元素。

从仓库源码看栈的底层实现

本解法中的stack = []在 Python 中本质是一个基于列表的顺序栈。仓库中的顺序栈实现示例清晰地展示了其底层机制：

class Stack: # 初始化空栈 def __init__(self, size=100): self.stack = [] self.size = size self.top = -1 # 入栈操作 def push(self, value): if self.is_full(): raise Exception('Stack is full') else: self.stack.append(value) self.top += 1 # 出栈操作 def pop(self): if self.is_empty(): raise Exception('Stack is empty') else: self.top -= 1 self.stack.pop() # 获取栈顶元素 def peek(self): if self.is_empty(): raise Exception('Stack is empty') else: return self.stack[self.top]

可以看到：push对应列表的append（尾部追加），pop对应列表的pop()（尾部弹出），peek对应stack[-1]访问栈顶。小行星碰撞解法正是直接使用 Python 列表的这三个 O(1) 操作完成栈模拟，无需自定义栈类。更完整的顺序栈与链式栈对比可参考栈基础章节。

此外，本题虽然不属于严格意义的单调栈问题，但「用栈顶与当前元素反复比较、不合条件即弹出」的过程与单调栈章节描述的「进栈时弹出所有不满足单调性的元素」的思想一脉相承——区别在于本题弹出条件还受「方向」和「大小比较」双重约束。

题目变式与同类练习

本题在仓库中还有一道几乎完全一致的变式题：LCR 037. 行星碰撞（力扣 LCR 037），题面与解题思路、代码完全一致，可作为本解的交叉验证。

掌握「栈模拟按方向成对消除」这一类题型后，可以继续挑战仓库中以下同族题目：

• 0020. 有效的括号：用栈匹配成对出现的括号，是栈模拟的入门经典；
• 0155. 最小栈：栈在 O(1) 时间内维护额外信息；
• 0150. 逆波兰表达式求值：用栈对操作数做运算；
• 0739. 每日温度：单调栈求右侧第一个更大元素，与本题「栈顶比较弹出」的模式最为接近；
• 0394. 字符串解码：栈处理嵌套结构。

本题在算法面试热门题目总表中被标注为「栈、数组、模拟，中等」难度，与每日温度同属 0700-0799 区间内的栈类模拟题，适合在掌握栈基础后作为进阶练习。

小结

LeetCode 0735「小行星碰撞」的精髓在于识别出「碰撞只发生在相邻相向小行星之间、且存在连锁反应」这一结构，从而自然联想到用栈维护「尚未被消灭的最近行星」。只需一次线性遍历，配合三条清晰的入栈/出栈判定规则，即可在 O(n) 时间内得到所有幸存小行星。把这道题的「方向 + 大小」双重判定逻辑吃透，栈模拟类的面试题基本可以一通百通。

• 教程
• 文档
• 知识库