跳至主要內容

剑指 Offer II 037. 小行星碰撞

ITCharge大约 2 分钟

剑指 Offer II 037. 小行星碰撞open in new window

  • 标签:栈、数组
  • 难度:中等

题目链接

题目大意

给定一个整数数组 asteroids,表示在同一行的小行星。

数组中的每一个元素,其绝对值表示小行星的大小,正负表示小行星的移动方向(正表示向右移动,负表示向左移动)。每一颗小行星以相同的速度移动。小行星按照下面的规则发生碰撞。

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

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

解题思路

用栈模拟小行星碰撞,具体步骤如下:

  • 遍历数组 asteroids
  • 如果栈为空或者当前元素 asteroid 为正数,将其压入栈。
  • 如果当前栈不为空并且当前元素 asteroid 为负数:
    • 与栈中元素发生碰撞,判断当前元素和栈顶元素的大小和方向,如果栈顶元素为正数,并且当前元素的绝对值大于栈顶元素,则将栈顶元素弹出,并继续与栈中元素发生碰撞。
    • 碰撞完之后,如果栈为空并且栈顶元素为负数,则将当前元素 asteroid 压入栈,表示碰撞完剩下了 asteroid
    • 如果栈顶元素恰好与当前元素值大小相等、方向相反,则弹出栈顶元素,表示碰撞完两者都爆炸了。
  • 最后返回栈作为答案。

代码

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