高频经典面试算法题-行星碰撞

题目

给定一个整数数组 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 向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞

提示：

解题思路

使用栈，每次拿栈顶元素来判断操作即可

代码实现

使用循环

var asteroidCollision = function (asteroids) {
  const stack = [];
  for (let aster of asteroids) {
    // 碰到负方向行星就会碰撞，看是否会消灭栈内的行星，如果被消灭就出栈
    while (stack.length && stack[stack.length - 1] > 0 && stack[stack.length - 1] < -aster) {
      stack.pop();
    }
    // 碰到一样大的负方向行星，被消灭出栈
    if (stack.length && aster < 0 && stack[stack.length - 1] === -aster) {
      stack.pop();
    } else if (aster > 0 || !stack.length || stack[stack.length - 1] < 0) {
      // 直接入栈的情况是 正方向行星或者之前没任何行星或者之前只有负方向行星永远不会碰撞
      stack.push(aster);
    }
  }
  return stack;
};

使用递归

/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function (asteroids) {
  if (asteroids.length === 0) return [];
  const stack = [asteroids[0]];

  const checkPush = (val) => {
    const top = stack[stack.length - 1];
    if (top > 0 && val < 0) {
      if (Math.abs(val) === top) {
        // 相等就消灭
        stack.pop();
        return;
      }
      stack.pop();
      const after = Math.abs(val) < top ? top : val;
      if (after < 0) {
        // 负数赢了检测是否要入栈
        checkPush(after);
      } else {
        // 正数赢了直接入栈
        stack.push(after);
      }
    } else {
      // 直接入栈
      stack.push(val);
    }
  };

  for (let i = 1; i < asteroids.length; i++) {
    const item = asteroids[i];
    checkPush(item);
  }
  return stack;
};