小行星碰撞

连锁碰撞类栈题：只有右行栈顶和左行当前元素会碰撞，因此需要 while 连续处理。

#resource / algorithm #type / snippet #status / growing #source / leetcode #ds / stack

[!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;
};

一句话总结

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