735 行星碰撞（模拟）

小咪咪 2022-09-10 04:28 172阅读 0赞

**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）  
链接：https://leetcode-cn.com/problems/asteroid-collision

**2. 思路分析：**

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

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

**3. 代码如下：**

from typing import List
    
    
    class 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