[!info] related notes 算法面试题型 MOC 栈

小行星碰撞

题目链接：https://leetcode.cn/problems/asteroid-collision/

题型判断

这是普通栈里的“碰撞 / 连锁消除”代表题，不要求栈内大小单调。数组顺序表示位置，非零整数的符号表示方向、绝对值表示大小，所有小行星速度相同。

真正会发生碰撞的情况只有一种：

• 栈顶小行星向右飞：top > 0
• 当前小行星向左飞：x < 0

也就是：

top > 0 && x < 0

核心思路

遍历当前小行星 x：

• 如果不会和栈顶碰撞，直接入栈
• 如果会碰撞，就不断比较大小
  • 栈顶绝对值更小：栈顶爆炸，继续碰
  • 一样大：两个都爆炸
  • 栈顶更大：当前爆炸

这里必须是 while，因为当前小行星可能连续撞碎前面多个小行星。

JavaScript

var asteroidCollision = function(asteroids) {
    const stack = [];

    for (const x of asteroids) {
        let alive = true;

        while (alive && stack.length && stack[stack.length - 1] > 0 && x < 0) {
            const top = stack[stack.length - 1];

            if (top < -x) {
                stack.pop();
            } else if (top === -x) {
                stack.pop();
                alive = false;
            } else {
                alive = false;
            }
        }

        if (alive) {
            stack.push(x);
        }
    }

    return stack;
};

每个元素最多入栈和出栈一次；失败碰撞也会结束当前元素的循环，因此总时间 O(n)，空间 O(n)。

一句话总结

碰撞不是“看前一个元素”，而是“当前元素可能连续作用于前面一串幸存者”。