【算法】行星碰撞

作者：lomtom 个人网站：lomtom.cn 你的支持就是我最大的动力。

题目难度：中等[1]

题目描述：

给定一个整数数组 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 。

限制及提示：

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

解题分析及思路：

本题可以遍历整个数组，然后将符合条件的值保存在栈里面，然后根据栈顶元素queue[len(queue)-1]和当前值num进行比较。

拿到题的第一想法就是通过栈顶元素queue[len(queue)-1]与当前遍历的元素num来判断两数是否为正负相反的两个数，然后再进行操作，但是这样还需要额外考虑-2, -1, 1, 2，这种情况其实不会发生碰撞。

其实，只需要将num的值进行判断即可：

• 当num为正数时，将其入栈。
• 当num为负数时，与栈顶元素queue[len(queue)-1]进行比较，其结果可以分为三种：
  • 当 -num 比queue[len(queue)-1]大时，栈顶行星爆炸，栈顶元素出栈，继续与栈顶元素比较，直到退出比较，退出比较后，如果当前行星存活，则入栈。
  • 当 -num 与queue[len(queue)-1]相等时，栈顶行星与当前行星爆炸，栈顶元素出栈，退出比较。
  • 当 -num 比queue[len(queue)-1]小时，当前行星爆炸，退出比较。

代码分析：

定义栈，并且定义比较的方法：

queue := make([]int, 0)
compareAndPush := func(num int) {
    for num < 0 && len(queue) > 0 && queue[len(queue)-1] > 0 {
        if -num > queue[len(queue)-1] { // 当 `-num` 比`queue[len(queue)-1]`大时，栈顶行星爆炸，栈顶元素出栈
            queue = queue[:len(queue)-1]
        } else if -num == queue[len(queue)-1] { // 当 `-num` 与`queue[len(queue)-1]`相等时，栈顶行星与当前行星爆炸，栈顶元素出栈，退出比较。
            queue = queue[:len(queue)-1]
            return
        } else { //当 `-num` 比`queue[len(queue)-1]`小时，当前行星爆炸，退出比较。
            return
        }
    }
    queue = append(queue, num)
}

遍历整个数组：

for index := range asteroids {
    compareAndPush(asteroids[index])
}

源代码：行星碰撞[2]

复杂度：

• 时间复杂度：O(n)，遍历数组所需时间。
• 空间复杂度：O(n)

执行结果：

• 执行用时：8 ms , 在所有 Go 提交中击败了 85.00% 的用户
• 内存消耗：4.4 MB , 在所有 Go 提交中击败了57.50%的用户

参考资料

[1]

行星碰撞: https://leetcode.cn/problems/asteroid-collision/

[2]

源码: https://github.com/lomtom/algorithm-go/blob/main/leetcode/735行星碰撞_test.go