735. 小行星碰撞
题目描述
输入整数数组 asteroids，按顺序表示排在一条直线上的小行星。元素的绝对值是小行星的大小，正数表示向右飞，负数表示向左飞，所有小行星速度相同。
只有向右飞的在左、向左飞的在右时，两者才会相撞。相撞时较小的那颗消失；大小相等则两颗都消失。同方向飞行的小行星永远不会相撞。
返回所有碰撞结束后剩下的小行星，保持它们原来的相对顺序。
示例 1
输入：asteroids = [5,10,-5] 输出：[5,10]
解释：10 撞毁 -5，5 和 10 同向不相撞。
示例 2
输入：asteroids = [8,-8] 输出：[]
解释：两者大小相同，同归于尽。
示例 3
输入：asteroids = [10,2,-5] 输出：[10]
解释：-5 先撞毁 2，再被 10 撞毁。
示例 4
输入：asteroids = [3,5,-6,2,-1,4] 输出：[-6,2,4]
解释：-6 撞毁 5 和 3 后继续向左；2 撞毁 -1；2 和 4 同向。
数据范围
2 <= asteroids.length <= 10^4-1000 <= asteroids[i] <= 1000asteroids[i] != 0
解题思路
只有“左边向右、右边向左”才会相撞。从左到右扫描，用栈保存目前存活的小行星。正数直接入栈；负数 a 会不断撞栈顶的正数：栈顶更小就弹出并继续撞，一样大就同归于尽，栈顶更大则 a 爆炸。如果栈空或栈顶也向左，a 存活入栈。
为什么正确
栈中的小行星互不碰撞：它们一定是若干个负数在前，若干个正数在后。
复杂度分析
时间 O(n)，每颗小行星至多入栈、出栈各一次；空间 O(n)。
易错点
负数在左、正数在右（如 [-2, 1]）是背向而行，不会碰撞。一颗负数可能连续撞碎多颗正数，要用循环而不是 if。大小相等时两颗都要消失。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
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()
continue
if stack[-1] == -a:
stack.pop()
alive = False
if alive:
stack.append(a)
return stackclass Solution {
public int[] asteroidCollision(int[] asteroids) {
int[] stack = new int[asteroids.length];
int top = 0;
for (int a : asteroids) {
boolean alive = true;
while (alive && a < 0 && top > 0 && stack[top - 1] > 0) {
if (stack[top - 1] < -a) {
top--;
continue;
}
if (stack[top - 1] == -a) {
top--;
}
alive = false;
}
if (alive) {
stack[top++] = a;
}
}
return Arrays.copyOf(stack, top);
}
}class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> stack;
for (int a : asteroids) {
bool alive = true;
while (alive && a < 0 && !stack.empty() && stack.back() > 0) {
if (stack.back() < -a) {
stack.pop_back();
continue;
}
if (stack.back() == -a) {
stack.pop_back();
}
alive = false;
}
if (alive) {
stack.push_back(a);
}
}
return stack;
}
};func asteroidCollision(asteroids []int) []int {
stack := []int{}
for _, a := range asteroids {
alive := true
for alive && a < 0 && len(stack) > 0 && stack[len(stack)-1] > 0 {
if stack[len(stack)-1] < -a {
stack = stack[:len(stack)-1]
continue
}
if stack[len(stack)-1] == -a {
stack = stack[:len(stack)-1]
}
alive = false
}
if alive {
stack = append(stack, a)
}
}
return stack
}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();
continue;
}
if (stack[stack.length - 1] === -a) {
stack.pop();
}
alive = false;
}
if (alive) {
stack.push(a);
}
}
return stack;
};function asteroidCollision(asteroids: number[]): number[] {
const stack: number[] = [];
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();
continue;
}
if (stack[stack.length - 1] === -a) {
stack.pop();
}
alive = false;
}
if (alive) {
stack.push(a);
}
}
return stack;
}