LeetCode LCR 037. 行星碰撞

约 5 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 栈 LCR 模拟

题目描述

✅ LCR 037. 行星碰撞

image-20260928235552967

image-20260928235552978

题意分析

数组顺序表示行星的左右位置，正数向右移动、负数向左移动，绝对值表示大小。所有行星速度相同，相撞时较小者消失，大小相等则一起消失，要求按原左右顺序返回最终存活者。

同向行星不会追上彼此，左负右正的两颗又会互相远离，因此只有“左侧正数、右侧负数”需要结算碰撞。一个较大的负数可能连续撞碎多个正数，必须处理完整条碰撞链。

解法：栈处理连锁碰撞

核心思路

[!blue]

从左到右扫描，用栈保存已处理前缀经过碰撞后剩下的行星，并保持它们的左右顺序。栈内部已经没有待碰撞的相向组合，但后续到来的负数仍可能撞碎栈中的正数。

当前行星为正数时，它与左侧存活者要么同向、要么互相远离，可以直接入栈。当前行星为负数 x 时，先遇到的是左侧最近的存活行星，也就是栈顶，因此按栈顶顺序逐个结算。

只要栈顶是比 -x 更小的正数，就把它弹出，继续检查新的栈顶。循环停止后，如果栈顶大小等于 -x，弹掉栈顶并丢弃当前行星；如果栈空或栈顶为负，当前行星没有相向阻挡，可以入栈；否则栈顶是更大的正数，当前行星被撞碎，不入栈。

每轮都先解决当前行星与已有前缀之间的全部可能碰撞，再决定是否把它加入，因此新的栈仍是当前前缀的稳定结果。扫描结束后不再有新行星加入，栈从底到顶就是最终答案。

解题步骤

  1. 初始化空栈，从左到右读取当前行星 x。
  2. 若 x > 0，直接入栈。
  3. 若 x < 0，循环弹出所有仍位于栈顶、向右且比它小的行星。
  4. 对循环后的状态分别处理同归于尽、无阻挡入栈、被更大正数撞碎三种情况。
  5. 保留栈底到栈顶的顺序输出。Java 以双端队列尾部为栈顶，迭代从头到尾恰好对应此顺序；Go 直接返回切片。

代码实现

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        // 栈里自底向上是已扫描部分最终存活的行星，顺序即答案顺序。
        Deque<Integer> stk = new ArrayDeque<>();

        for (int x : asteroids) {
            if (x > 0) {
                // 向右飞，与左侧任何存活行星都不会相遇。
                stk.offerLast(x);
            } else {
                // 连锁撞碎所有更小的右飞行星。
                while (!stk.isEmpty() && stk.peekLast() > 0 && stk.peekLast() < -x) {
                    stk.pollLast();
                }

                if (!stk.isEmpty() && stk.peekLast() == -x) {
                    // 大小相等，同归于尽，当前行星也不入栈。
                    stk.pollLast();
                } else if (stk.isEmpty() || stk.peekLast() < 0) {
                    // 左边已无阻挡，或栈顶同向，当前行星存活。
                    stk.offerLast(x);
                }
                // 其余情形：栈顶是更大的正数，当前行星被撞碎，直接丢弃。
            }
        }

        return stk.stream().mapToInt(Integer::valueOf).toArray();
    }
}

func asteroidCollision(asteroids []int) (stk []int) {
    // 栈里自底向上是已扫描部分最终存活的行星，顺序即答案顺序。
    for _, x := range asteroids {
        if x > 0 {
            // 向右飞，与左侧任何存活行星都不会相遇。
            stk = append(stk, x)
        } else {
            // 连锁撞碎所有更小的右飞行星。
            for len(stk) > 0 && stk[len(stk)-1] > 0 && stk[len(stk)-1] < -x {
                stk = stk[:len(stk)-1]
            }
            if len(stk) > 0 && stk[len(stk)-1] == -x {
                // 大小相等，同归于尽，当前行星也不入栈。
                stk = stk[:len(stk)-1]
            } else if len(stk) == 0 || stk[len(stk)-1] < 0 {
                // 左边已无阻挡，或栈顶同向，当前行星存活。
                stk = append(stk, x)
            }
            // 其余情形：栈顶是更大的正数，当前行星被撞碎，直接丢弃。
        }
    }
    return
}

复杂度分析

  • 时间复杂度：$O(n)$。每颗行星最多入栈一次、出栈一次，所有连锁碰撞循环的弹栈次数合计不超过 n；输出也是线性。
  • 空间复杂度：$O(n)$，没有碰撞时栈会保存全部行星。

关键点总结

[!green]

  • 只有左正右负的组合会相遇，碰撞条件同时依赖方向和左右位置。
  • 栈顶是当前行星最先遇到的存活对手，弹出后才能暴露更远的对手。
  • 栈表示已扫描前缀的稳定结果，不能把它理解为已经保证全局存活。
  • 单次可能连续弹出多颗，但每颗只会消失一次，因此总时间仍为线性。

易错点总结

[!yellow]

  • 不能让左负右正或同向行星相互消除，它们不会发生碰撞。
  • 连锁碰撞必须用循环，一次弹栈后可能仍有更远的正数需要比较。
  • 相等时两颗都消失，弹掉栈顶后不能再把当前行星加入。
  • 负数比较的是大小 -x，循环还必须保证栈顶为正；最终输出不能颠倒原左右顺序。

相似题目

题目 难度 关联与区别
1047. 删除字符串中的所有相邻重复项 简单 同样用栈保存仍存活的前缀，新元素可能触发连续消除，本题需额外判断方向和绝对值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/72303611
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！