剑指 Offer II 037. 小行星碰撞

概要

用栈处理相邻两颗行星是否碰撞。

题目

给定一个整数数组 asteroids，表示在同一行的小行星。

对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。

找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

链接：https://leetcode.cn/problems/XagZNi

思路

有点意思。

实际上是，比较相邻的两个值，先看正负号。

• 如果符号相同，则都保留。
• 如果符号相反
  • 前者为负，后者为正，则两不冲突，都保留。
  • 前者为正，后者为负，则绝对值大的那个数字保留。

第一个想法是，可以在数组中两两匹配去处理，但是对于数组的移除元素，或者重复利用之前出现的元素，还是比较麻烦的。

最关键的是，你在后面遇到的小行星，还会继续往前撞你呀。

这里还是使用栈。

解法：栈

代码

public int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();
    int i = 0;
    while (i < asteroids.length) {
        int current = asteroids[i];
        // 栈空的时候，直接入栈
        if (stack.size() == 0) {
            stack.push(current);
            i++;
            continue;
        }

        int peek = stack.peek();
        if (peek > 0 && current < 0) {
            // 发生碰撞的情况
            int result = peek + current;
            // 比较二者绝对值
            if (result < 0) {
                // 栈顶绝对值小，则被碰撞爆炸，出栈
                stack.pop();
            } else if (result == 0) {
                // 同归于尽
                stack.pop();
                i++;
            } else {
                i++;
            }
        } else {
            stack.push(current);
            i++;
        }
    }
    int[] result = new int[stack.size()];
    for (int j = result.length - 1; j >= 0; j--) {
        result[j] = stack.pop();
    }
    return result;
}

提交结果

上面的判断过于啰嗦，简化了一下代码，如下：

public int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();
    int i = 0;
    while (i < asteroids.length) {
        int current = asteroids[i];
        // 栈空的时候，直接入栈
        if (stack.isEmpty() || stack.peek() < 0 || current > 0) {
            stack.push(current);
            i++;
            continue;
        }
        int peek = stack.peek();
        // 只有栈顶为正数，当前元素为负数，才会发生碰撞的情况
        if (peek <= -current) {
            // 栈顶绝对值小，则被碰撞爆炸，出栈
            stack.pop();
            if (peek < -current) {
                continue;
            }
        }
        i++;
    }
    int[] result = new int[stack.size()];
    for (int j = result.length - 1; j >= 0; j--) {
        result[j] = stack.pop();
    }
    return result;
}

啊这，耗时和内存都增加了……