难度：★★★☆☆
类型：数组
方法：栈
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给定一个整数数组 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 向右移动。
由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。
说明:
数组 asteroids 的长度不超过 10000。
每一颗行星的大小都是非零整数，范围是 [-1000, 1000] 。
解答
行星排列的方式是一维数组，并且通过相邻的元素之间的关系进行状态的变化，因此这道题适合用栈的数据结构来做。
定义一个栈ans，用来存储当前各个行星的状态。将各个行星按照顺序添加到栈中，但是在添加的过程中，需要及时的做判断，而且各个情况都要考虑周到。
我们现有的信息是，所有行星的质量和运动的方向，根据题目的要求，行星的碰撞需要的条件是：
- 两个行星是相邻的；
- 左边的行星是向右运动的，右边的行星是向左运动的。
因此，在程序运行的过程中，需要随时的考虑栈顶元素与当前新加入的行星之间的运动方向，一旦它们的运动是相向而行的，则启动碰撞程序，这里用while循环实现。
一旦启动碰撞程序，需要根据发生碰撞的两个行星之间的相对质量，给出碰撞决策。按照题目的要求，实际上就三种情况，左边的行星（栈顶的行星）爆炸，右边的行星（当前遍历到的新行星）爆炸，或者两个行星都爆炸。对于右边的行星爆炸是比较好处理的，直接跳过这个行星，研究下一个就好（程序上用break跳出碰撞程序），如果左边的行星爆炸，需要把栈顶的行星弹出，但是需要注意，这时还不能退出碰撞程序，因为当前研究的新行星可能会继续向左运动，依然有可能发生继续的碰撞，因此需要继续进行栈顶行星与新行星的比较，直到跳出碰撞程序。
综上，碰撞程序的进入与跳出都是有条件的。进入碰撞程序的条件是栈顶行星与新行星的相向而行，跳出碰撞程序的条件是新行星因为碰撞爆炸或新行星与栈顶行星是成为同一方向（一样的符号）。
这里还需要注意一点，在代码的编写上，当栈为空时的特殊情况需要处理，而且入栈也是需要条件的，这里while else语句的使用是有必要的。
class Solution:
def asteroidCollision(self, asteroids):
result = []
for asteroid in asteroids:
while result and result[-1] > 0 > asteroid: # 如果行星向右，而右边相邻的行星向左运动
if abs(result[-1]) > abs(asteroid): # 如果栈顶行星质量比较大，则新加入的小行星爆炸，继续下一个行星
break # 如果栈顶行星质量和新的行星一样，则一起爆炸，弹出当前行星的同时，继续下一个行星
elif abs(result[-1]) == abs(asteroid):
result.pop()
break
else: # 如果栈顶行星质量比新加入的小，则当前行星爆炸，继续查看是否有更多的列表中的行星爆炸
result.pop()
else:
result.append(asteroid)
return result
if __name__ == "__main__":
a = [-5, -10, -5, 5, 5, -6, 6, -6]
s = Solution()
print(s.asteroidCollision(a))
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
网友评论