# 0735. 行星碰撞
### 题目地址(735. 行星碰撞)
### 题目描述
```
给定一个整数数组 asteroids，表示在同一行的行星。
对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
示例 1：
输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
示例 2：
输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。
示例 3：
输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
示例 4：
输入：asteroids = [-2,-1,1,2]
输出：[-2,-1,1,2]
解释：-2 和 -1 向左移动，而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。
提示：
2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
```
### 前置知识
* 栈
### 公司
* 暂无
### 思路
这道题思考难度不大。不过要想一次 bug free 也并不简单。我做这道题就错了好几次。
不妨从左到右进行**模拟**，这样只需要考虑其是否和左边的星球相撞即可，而不需要考虑右边（想想为什么？）。
如果当前星球的速度是正的。那么永远不会和前面的星球相撞，直接入栈。 否则，其有可能和前面的星球相撞。具体来说，如果前面的星球速度也是负数就不会相撞。反之如果前面星球速度为正，那么就一定会相撞。
而具体的相撞结果有三种（根据题目的例子也可以知道）：
1. 两个星球速度绝对值一样，那么两个星球都碎了。即出栈一次，不进栈。
2. 负速度的绝对值大，那么就出栈一次，且进栈
3. 正速度的绝对值大，那么就不出栈也不进栈。
唯一需要注意的是，如果发生碰撞后，当前的星球（速度为负的星球）速度绝对值更大，那么需要继续判断其是否会和前前一个星球碰撞。这提示我们使用 while 循环来进行。
思路其实还是蛮清晰的。只不过一开始追求代码简洁写了一些 bug。之后不得不认真考虑各种情况，写了一些“”丑代码“。
### 关键点
* while break if else 的灵活使用
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def asteroidCollision(self, asteroids):
stack = []
for asteroid in asteroids:
if not stack or asteroid > 0:
stack.append(asteroid)
else:
while stack and stack[-1] > 0:
if stack[-1] + asteroid > 0:
break
elif stack[-1] + asteroid < 0:
# 这种情况需要继续和前前星球继续判断是否碰撞
stack.pop()
else:
stack.pop()
break
else:
stack.append(asteroid)
return stack
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/735.asteroid-collision.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.