行星碰撞问题为什么适合用栈模拟？

简化版

行星碰撞用栈保存已经稳定存在的行星。只有栈顶向右移动且当前行星向左移动时才会碰撞；比较绝对值，小的爆炸，相等都爆炸，当前行星如果没爆炸才入栈。

详细版

正数表示向右，负数表示向左。新行星从左到右扫描时，只可能和栈顶的右行星发生碰撞，因为更左侧的行星被栈顶挡住。循环处理连续碰撞，直到当前行星爆炸、栈空，或栈顶不再可能碰撞。

int[] asteroidCollision(int[] asteroids) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int a : asteroids) {
        boolean alive = true;
        while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) {
            int top = stack.peek();
            if (top < -a) stack.pop();
            else if (top == -a) { stack.pop(); alive = false; }
            else alive = false;
        }
        if (alive) stack.push(a);
    }
    int[] ans = new int[stack.size()];
    for (int i = ans.length - 1; i >= 0; i--) ans[i] = stack.pop();
    return ans;
}

关键条件是 stack.peek() > 0 && a < 0，同向或背向而行都不会碰撞。

完整版教学

一、什么时候会发生碰撞

行星按数组顺序从左到右排列，正数向右，负数向左。只有左边的行星向右、右边的新行星向左时，它们才会迎面相撞。也就是栈顶 > 0 且当前 a < 0。

左  ->      <-  右    会碰撞
左  <-      ->  右    越走越远，不碰撞
左  ->      ->  右    同向，不碰撞
左  <-      <-  右    同向，不碰撞

这个条件如果写错，会让很多本不该碰撞的情况被误删。

二、栈保存的是什么

栈保存已经扫描过、在当前视角下还存活的行星。新行星只需要和栈顶比较，因为栈顶是距离它最近的左侧存活行星；如果栈顶被撞碎，当前行星才有机会继续和更左边的下一个栈顶碰撞。

例如 [10,2,-5]：-5 先撞 2，2 爆炸；然后 -5 继续撞 10，自己爆炸。这个连续过程正好是 while 弹栈。

三、三种碰撞结果

碰撞双方大小按绝对值比较：

情况	结果	当前行星是否继续
`top < -a`	栈顶爆炸	当前继续向左撞
`top == -a`	双方爆炸	当前结束
`top > -a`	当前爆炸	当前结束

这里 a 是负数，所以当前行星大小是 -a。写成 Math.abs(a) 也可以，但要注意不要混淆方向和大小。

四、手算示例

以 [5,10,-5] 为例，5 和 10 入栈后，-5 只会撞 10。因为 10 更大，-5 爆炸，结果 [5,10]。

再看 [8,-8]，-8 撞 8，大小相等，两个都爆炸，结果 []。

[10, 2, -5]
栈 [10,2]
-5 撞 2 -> 2 爆
-5 撞 10 -> -5 爆
结果 [10]

这类题最重要的是把连续碰撞模拟完整。

五、结果顺序怎么恢复

如果用 push 把元素放到栈顶，最终栈顶是数组右侧的行星。输出时要从结果数组末尾向前填，才能恢复从左到右的顺序。

int[] ans = new int[stack.size()];
for (int i = ans.length - 1; i >= 0; i--) {
    ans[i] = stack.pop();
}

也可以用 offerLast / pollLast 把双端队列当作尾部栈使用，最后按队列顺序遍历，关键是保持方向一致。

六、常见误区与追问

记忆钩子：只看“栈顶向右、当前向左”这一种迎面相撞。撞碎栈顶就继续撞，当前碎了就停。

误区：一正一负就一定碰撞。 [-2,1] 是背向而行，不会碰撞。
误区：当前行星只碰撞一次。 它可能撞碎多个较小的右行星，需要 while。
误区：相等时只弹栈顶。 大小相等双方都爆炸，当前不能入栈。
追问：为什么只和栈顶比较？ 栈顶是最近的左侧存活行星，更左边的行星被它挡住。
追问：复杂度为什么 O(n)？ 每个行星最多入栈一次、出栈一次，总操作线性。
追问：如果有速度差怎么办？ 本题默认速度相同；若速度不同，就变成事件模拟，不能直接套这个栈模型。

七、加强记忆

行星碰撞不是全局两两比较，而是从左到右维护“已稳定区域”。当前负行星只可能冲进左侧正行星堆，所以栈顶正数和当前负数是唯一碰撞入口。比较大小决定谁爆，当前活着就继续撞，最后活着才入栈。

简化版

详细版