735 行星碰撞（模拟）

行星碰撞（模拟）"/>

735 行星碰撞（模拟）

1. 问题描述：

给定一个整数数组 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 <= 10 ^ 4
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
来源：力扣（LeetCode）
链接：

2. 思路分析：

分析题目可以知道最终的结果是左边的行星一直往左走，右边的行星一直往右走，并且一定是先处理相邻的行星，对于当前的行星x的走向与质量分情况讨论即可，因为使用的是python语言所以我们可以使用列表进行模拟，设当前列表中最后一个元素为y，当前行星质量为x：

• x向右走，保留x
• x向左走，列表中的元素向右，这个时候需要弹出所有质量小于x的行星，这个是一个循环的过程，当循环结束之后有以下几种情况：
  • 列表中的最后一个元素质量等于x，弹出列表最后一个元素
  • 列表此时为空，说明所有列表中所有行星质量小于x，那么保留x
• 列表为空或者x向左走，列表的上一个元素也向左走，保留x

3. 代码如下：

from typing import Listclass Solution:def asteroidCollision(self, asteroids: List[int]) -> List[int]:res = list()for x in asteroids:if x > 0: res.append(x)else:# 弹出所有向右走并且质量小于当前行星x的行星while res and 0 < res[-1] < -x: res.pop()# 两个行星质量相等则两者都消失if res and res[-1] == -x: res.pop()# x的上一个行星向左走或者没有行星了elif not res or res[-1] < 0: res.append(x)return res