735. Asteroid Collision

Leetcode link

题目简介

/**
 * @param {number[]} asteroids
 * @return {number[]}
 */

题目给我们一个数字数组表示一群行星，数组元素代表行星的大小，正负值代表行星前进方向，每个行星前进速度一致

如果大行星碰到小行星，则小行星消失、如果两个相同大小的碰撞则都消失

要求我们最后计算出来剩下的元素有哪些

解题思路

这题需要用到栈来求解，用一个栈 stack 来维护当前的行星

我们正常遍历数组，有三种情况我们可以直接入栈：

1. 当前栈为空
2. 当前栈顶是负的
3. 当前遍历元素是正的

接下来我们需要考虑栈顶为正且当前遍历元素为负的情况，一共有三种：

1. stack[stack.length - 1] > -asteroids[i]：栈顶比当前行星大，不需要做什么操作继续遍历
2. stack[stack.length - 1] < -asteroids[i]：栈顶比当前行星小，需要出栈并且重新遍历当前行星一次
3. stack[stack.length - 1] === -asteroids[i]：两个同体积行星碰撞，都消失，直接出栈当前栈顶即可

最后返回该栈即可

Javascript

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

    for (let i = 0; i < asteroids.length; i++) {
        const top = stack[stack.length - 1]
        const cur = asteroids[i]

        if(top === undefined || top < 0 || cur > 0 ) {
            stack.push(cur)
        } else if(-cur === top) {
            stack.pop()
        } else if(top < -cur){
            stack.pop()
            // check this asteroid again
            i--
        }
    }

    return stack
};