【leetcode】小行星碰撞

一、题目描述

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

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

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

输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。

二、代码思路

• 有这样几种情况需要注意
• 1、+ - 则会发生碰撞
• 1.1 - > + ，- 会接着向左碰撞，直到被撞没，要不直接撞到底，而且撞得时候会不断对数组后面的元素进行破坏。（其实这里就能联想到栈）
• 2、+ — + 则 - 只会和左边的 - 碰撞，无论碰撞结果如何都不会和后面撞
• 3、+ - - 则第一个 - 会和 + 撞，而且如果撞击后结果是 + ，则还会发生碰撞如果撞击结果是负的或者==0则没事儿

当然，我刚开始是这莫想的，但是实现起来分情况来code，是在过于复杂，所以官方题解就很清晰明了：

使用栈 st 模拟小行星碰撞，从左往右遍历小行星数组 asteroids，当我们遍历到小行星 aster 时，使用变量 alive 记录小行星 aster 是否还存在（即未爆炸）。

当小行星aster 存在且 aster<0，栈顶元素非空且大于 00 时，说明两个小行星相互向对方移动：如果栈顶元素大于等于 −aster，则小行星 aster 发生爆炸，将 alive 置为 false；如果栈顶元素小于等于 −aster，则栈顶元素表示的小行星发生爆炸，执行出栈操作。重复以上判断直到不满足条件，如果最后 alive 为真，说明小行星 aster 不会爆炸，则将aster 入栈。

三、代码题解

package leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/*
 * @author lzy
 * @version 1.0
 * */
public class asteroid_ {
    public int[] asteroidCollision(int[] asteroids) {
        //首先分析一下
        //有几种情况：1、+ - 则会发生碰撞
//                      1.1 - > + ，- 会接着向左碰撞，直到被撞没，要不直接撞到底
//                   2、+ — + 则 - 只会和左边的 - 碰撞，无论碰撞结果如何都不会和后面撞
//                   3、+ - - 则第一个 - 会和 + 撞，而且如果撞击后结果是 + ，则还会发生碰撞
//                      如果撞击结果是负的或者==0则没事儿
        //所以我们初步使用双指针操作
        //分别标记，撞击元素的后一个元素以及撞击之后剩下的第一个元素

        Deque<Integer> stack = new ArrayDeque<Integer>();
        //我怎么，没想过用栈呢？
        //这道题，有一点我一直不理解：
        //就是+ -这种情况，如果 - 比 + 大那么，他可能就会一直倒着往左走来比较，这种情况，我竟不知道该如何模拟
        //其实这种情况，不就是个栈吗？！
        for (int item : asteroids) {
            //如此循环将item与栈中的元素进行比较，模拟就是+ -这种情况，如果 - 比 + 大那么，他可能就会一直倒着往左走来比较
            //这种情况，直到条件不符合
            boolean flag = true;
            while (flag && item < 0 && !stack.isEmpty() && stack.peek() > 0) {
                flag = stack.peek() >= -item;//如果栈顶元素大于该item绝对值，那么该item要被毁灭，所以flag应为false
                flag = !flag;
                if (-item >= stack.peek()) {
                    stack.pop();
                }
            }
            //如果该小行星没被毁灭，那么将其加入栈中
            if (flag == true) {
                stack.push(item);
            }
        }
        int res[] = new int[stack.size()];
        for (int i = stack.size() - 1; i >= 0; i--) {
            res[i] = stack.pop();
        }
        return res;
    }
}

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49