面试算法37：小行星碰撞

题目

输入一个表示小行星的数组，数组中每个数字的绝对值表示小行星的大小，数字的正负号表示小行星运动的方向，正号表示向右飞行，负号表示向左飞行。如果两颗小行星相撞，那么体积较小的小行星将会爆炸最终消失，体积较大的小行星不受影响。如果相撞的两颗小行星大小相同，那么它们都会爆炸消失。飞行方向相同的小行星永远不会相撞。求最终剩下的小行星。例如，有6颗小行星[4，5，-6，4，8，-5]，如图6.2所示（箭头表示飞行的方向），它们相撞之后最终剩下3颗小行星[-6，4，8]。

分析

下面以一个具体的例子来分析小行星碰撞的规律。先假设有6颗小行星[4，5，-6，4，8，-5]，然后逐一分析它们的飞行情况。第1颗是向右飞行的大小为4的小行星。此时还不知道它会不会和其他小行星碰撞，可以先将它保存到某个数据容器中。第2颗还是一颗向右飞行的小行星，它的大小为5。它和前面一颗小行星的飞行方向相同，所以不会碰撞。但现在还不知道它会不会和后面的小行星碰撞，因此也将它保存到数据容器中。第3颗是一颗向左飞行的小行星，大小为6。由于它和前面两颗小行星是相向而行的，因此会和前面两颗小行星相撞。由于大小为5的小行星离它更近，因此这两颗小行星将会先相撞。先后向数据容器中保存了大小为4、5的两颗小行星，后保存到数据容器中的小行星先和其他的小行星相撞。

根据题目的碰撞规则，小的小行星将会爆炸消失，因此当大小分别为5和6的两颗小行星相撞时，大小为5的小行星会爆炸消失。大小为6的小行星继续向左飞行，它将和大小为4的小行星相撞。大小为4的小行星爆炸消失，留下大小为6的小行星向左飞行。此时左边已经没有更多的小行星和这颗大小为6的小行星相撞，将它入栈。

接下来是两颗向右飞行的小行星，大小分别为4和8，它们和大小为6的小行星背向飞行，肯定不会相撞，因此将它们也先后入栈。最后是一颗大小为5向左飞行的小行星。此时栈中保存了3颗小行星[-6，4，8]，大小为8的小行星离它最近而且相向飞行，因此它将与大小为8的小行星相撞，然后爆炸消失。最终剩下3颗小行星[-6，4，8]。

解

public class Test {
    public static void main(String[] args) {
        int[] tokens = {4, 5, -6, 4, 8, -5};
        int[] result = asteroidCollision(tokens);
        for (int res : result) {
            System.out.println(res);
        }
    }

    public static int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int as : asteroids) {
            while (!stack.empty() && stack.peek() > 0 && stack.peek() < -as) {// 为什么while循环，是因为as没有被撞碎，接着撞
                stack.pop();
            }

            if (!stack.empty() && stack.peek() > 0 && stack.peek() == -as) {// 为什么没有while循环，是因为as被撞碎了
                stack.pop();
            }
            else if (as > 0 || stack.empty() || stack.peek() < 0) {
                stack.push(as);
            }
            // 如果不符合上述情况，则这里表示as被撞碎了，继续分析下一颗行星
        }

        return stack.stream().mapToInt(i -> i).toArray();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28