0735. 小行星碰撞【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 栈

1. 📝 题目描述

• leetcode

给定一个整数数组 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。

---

提示：

• 2 <= asteroids.length <= 10^4
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

2. 🎯 s.1 - 栈

c

int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize) {
    int* stack = (int*)malloc(sizeof(int) * asteroidsSize);
    int top = 0;
    for (int i = 0; i < asteroidsSize; i++) {
        int a = asteroids[i];
        int alive = 1;
        while (alive && a < 0 && top > 0 && stack[top - 1] > 0) {
            if (stack[top - 1] < -a) top--;
            else if (stack[top - 1] == -a) { top--; alive = 0; }
            else alive = 0;
        }
        if (alive) stack[top++] = a;
    }
    *returnSize = top;
    return stack;
}

js

/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function (asteroids) {
  const stack = []
  for (const a of asteroids) {
    let alive = true
    while (alive && a < 0 && stack.length && stack[stack.length - 1] > 0) {
      if (stack[stack.length - 1] < -a) stack.pop()
      else if (stack[stack.length - 1] === -a) {
        stack.pop()
        alive = false
      } else alive = false
    }
    if (alive) stack.push(a)
  }
  return stack
}

py

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        for a in asteroids:
            alive = True
            while alive and a < 0 and stack and stack[-1] > 0:
                if stack[-1] < -a:
                    stack.pop()
                elif stack[-1] == -a:
                    stack.pop()
                    alive = False
                else:
                    alive = False
            if alive:
                stack.append(a)
        return stack

• 时间复杂度：$O(n)$，其中 n 是小行星数量
• 空间复杂度：$O(n)$

算法思路：

• 用栈模拟碰撞过程，只有栈顶向右（正）且当前向左（负）时才碰撞
• 碰撞时比较绝对值：小的爆炸、相等都爆、大的存活
• 其余情况直接入栈