行星碰撞

Tips

题目类型: Stack

题目

给定一个整数数组 asteroids, 表示在同一行的行星.

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

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

示例

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

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

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

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

题解

一开始写了个菜鸡解法, 但确实太菜了... 这道题最优做法是使用栈.

使用栈 stack 模拟行星碰撞, 从左往右遍历行星数组 asteroids, 当我们遍历到行星 asteroid 时, 使用变量 alive 记录该行星 asteroid 是否还存在(即未爆炸).

当行星 asteroids 存在且 asteroids < 0, 栈顶元素存在且大于 0 时, 说明两个行星相互向对方移动:

• 如果栈顶元素大于等于 -asteroid, 则行星 asteroid 发生爆炸, 说明这颗行星不能被加入到栈中, 故将 alive 置为 false;
• 如果栈顶元素小于等于 -asteroid, 则栈顶元素表示的行星发生爆炸, 执行出栈操作. 重复以上判断直到不满足条件, 如果最后 alive 为真, 说明行星 asteroid 不会爆炸, 则将 asteroid 入栈.

菜鸡解法

/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function (asteroids) {
  let i = 0,
    j = 1

  while (j < asteroids.length) {
    const asteroidLeft = asteroids[i]
    const asteroidRight = asteroids[j]

    // 如果左边是往左的, 右边是往右的, 说明它们永远不会碰撞
    // 如果它们是同向的, 也不会发生碰撞
    if (
      (asteroidLeft < 0 && asteroidRight > 0) ||
      Math.sign(asteroidLeft) === Math.sign(asteroidRight)
    ) {
      i++
      j++
      // 如果发生碰撞
    } else {
      const asteroidLeftUsize = Math.abs(asteroidLeft)
      const asteroidRightUsize = Math.abs(asteroidRight)

      // 如果相等, 两个都删除掉
      if (asteroidLeftUsize === asteroidRightUsize) {
        asteroids.splice(j, 1)
        asteroids.splice(i, 1)
        // 左边的小就删除左边的
      } else if (asteroidLeftUsize < asteroidRightUsize) {
        asteroids.splice(i, 1)
        // 右边的小就删除右边的
      } else {
        asteroids.splice(j, 1)
      }

      // i 和 j 需要复位, 因为 asteroids 本身的 length 发生了变化
      i = 0
      j = 1
    }
  }

  return asteroids
}

JavaScript

/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function (asteroids) {
  const stack = []

  for (const asteroid of asteroids) {
    let alive = true

    while (
      alive &&
      // 当前 asteroid 往左走
      asteroid < 0 &&
      stack.length > 0 &&
      // 上一个往右走, 才会发生碰撞
      stack[stack.length - 1] > 0
    ) {
      const last = stack[stack.length - 1],
        curr = -asteroid

      alive = last < curr
      if (last <= curr) stack.pop()
    }

    if (alive) {
      stack.push(asteroid)
    }
  }

  return stack
}

Rust

pub fn asteroid_collision(asteroids: Vec<i32>) -> Vec<i32> {
    let mut stack = vec![];
    for asteroid in asteroids {
        let mut alive = true;

        while alive && asteroid < 0 && !stack.is_empty() && *stack.last().unwrap() > 0 {
            let last = *stack.last().unwrap();
            let curr = -asteroid;

            alive = curr > last;
            if curr >= last {
                stack.pop();
            }
        }

        if alive {
            stack.push(asteroid);
        }
    }

    stack
}