剑指offer

剑指offer037-小行星碰撞

小行星碰撞

Posted by 高明 on 2020-01-01

剑指offer037-小行星碰撞

题目

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

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

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

 

示例 1：

输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

示例 2：

输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。

示例 3：

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

示例 4：

输入：asteroids = [-2,-1,1,2]
输出：[-2,-1,1,2]
解释：-2 和 -1 向左移动，而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。

 

提示：

  • 2 <= asteroids.length <= 104
  • -1000 <= asteroids[i] <= 1000
  • asteroids[i] != 0

 

注意：本题与主站 735 题相同： https://leetcode-cn.com/problems/asteroid-collision/

Related Topics
  • 栈
  • 数组

  • 👍 12
  • 👎 0

    • 思路

    一开始想用两个栈实现，一个栈存负数的下标，一个栈存正数的下标，写到后面越来越烦

    慢慢觉得问题可以简化

    首先考虑开头是负数的场景，如 -1 -2 -3 1 2 3

    其实前面的负数已经走到头了，没有人会再和他们融合

    所以记录开始位置

    1
    2
    3
    4
    int index = 0;
    while (index < asteroids.length && asteroids[index] < 0) {
        index++;
    }

    从第一个正数开始，我们维护一个为正数的栈（除非有一个很大的负数，导致所有正数都被消除）

    当数字为正数时，直接入栈即可

    当数据为负数时，我们要从栈顶中拿出数(pop)与(i)进行PK

    比如 10，2，-5
    （3）-5即将入栈，开始PK
    2 （2）2入栈
    10 （1）10入栈

    直到我们可以消除-5，获取-5消除了所有的正数，到了栈底部

    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
    Stack<Integer> stack = new Stack<>();

    for (int i = index; i < asteroids.length; i++) {
        if (asteroids[i] > 0) {
            // 如果是正数，直接入栈 10入栈，2入栈
            stack.push(asteroids[i]);
        } else {
            // 如果是负数 t=-5
            int t = asteroids[i];
            // 每次pk最后选择的数字如果还是小于0，我们需要继续比较
            while (t < 0 && !stack.isEmpty()) {
                // 拿出栈中的第一个正数 2
                Integer peek = stack.peek();
                // 如果第一个数是负数，说明已经结束了，我们不需要比较
                if (peek < 0) {
                    break;
                } else if (peek > 0) {
                    // 如果是正数
                    // PK一下
                    t = pick(peek, t);
                    if (t == 0) {
                        // 如果相等，说明两者消除了，我们放弃这两个数
                        stack.pop();
                        break;
                    } else if (t > 0) {
                        // 如果t大于0，说明队列中的数赢了，我们放弃负数
                        break;
                    } else if (t < 0) {
                        // 如果t小于0，说明队列中数输了，我们移除2，继续将-5和10进行比较
                        stack.pop();
                    }
                }
            }
        }
    }

    除此之外，当一直比较下去，会出现最后的负数没有加入进去

    比如10，2，-100

    -100经过两次PK，都赢了，我们应该把它放入队列

    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
    for (int i = index; i < asteroids.length; i++) {
        if (asteroids[i] > 0) {
            stack.push(asteroids[i]);
        } else {
            int t = asteroids[i];
            boolean flag = true;
            while (t < 0 && !stack.isEmpty()) {
                Integer peek = stack.peek();
                if (peek < 0) {
                    break;
                } else if (peek > 0) {
                    t = pick(peek, t);
                    if (t == 0) {
                        stack.pop();
                        flag = false;
                        break;
                    } else if (t > 0) {
                        flag = false;
                        break;
                    } else if (t < 0) {
                        stack.pop();
                    }
                }
            }
            if (flag) {
                stack.push(asteroids[i]);
            }
        }
    }

    最后统计一下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int n = index + stack.size();
    int[] res = new int[n];
    for (int i = 0; i < index; i++) {
        res[i] = asteroids[i];
    }
    while (n > index) {
        res[n - 1] = stack.pop();
        n = n - 1;
    }
    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
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    class Solution {
        public int[] asteroidCollision(int[] asteroids) {
            int index = 0;
            while (index < asteroids.length && asteroids[index] < 0) {
                index++;
            }

            Stack<Integer> stack = new Stack<>();

            for (int i = index; i < asteroids.length; i++) {
                if (asteroids[i] > 0) {
                    stack.push(asteroids[i]);
                } else {
                    int t = asteroids[i];
                    boolean flag = true;
                    while (t < 0 && !stack.isEmpty()) {
                        Integer peek = stack.peek();
                        if (peek < 0) {
                            break;
                        } else if (peek > 0) {
                            t = pick(peek, t);
                            if (t == 0) {
                                stack.pop();
                                flag = false;
                                break;
                            } else if (t > 0) {
                                flag = false;
                                break;
                            } else if (t < 0) {
                                stack.pop();
                            }
                        }
                    }
                    if (flag) {
                        stack.push(asteroids[i]);
                    }
                }
            }

            int n = index + stack.size();
            int[] res = new int[n];
            for (int i = 0; i < index; i++) {
                res[i] = asteroids[i];
            }
            while (n > index) {
                res[n - 1] = stack.pop();
                n = n - 1;
            }
            return res;
        }

        public int pick(int x, int y) {
            if (x == -y) {
                return 0;
            } else if (x > 0 && y < 0) {
                return x > -y ? x : y;
            } else if (x < 0 && y > 0) {
                return y > -x ? y : x;
            } else {
                return 0;
            }
        }
    }
    1
    2
    3
    解答成功:
    执行耗时:5 ms,击败了77.12% 的Java用户
    内存消耗:38.9 MB,击败了87.64% 的Java用户
    FEATURED TAGS
    剑指offer
    FRIENDS