lc剑指 Offer II 037. 小行星碰撞（栈）

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

class Solution {
    /**
    什么情况需要入栈
    1.栈为空
    2.栈顶元素为负数(如果当前元素是负数就一起往左不会碰撞，为正数相反也不会碰撞)
    3.当前元素为正数(如果栈顶元素为负数就会相反，为正数也不会碰撞)
    细节：
    当判断栈顶元素小于等于当前元素（相反数）时
        等于直接弹出，也不会入栈
        小于就continue继续进行判断当前元素（根据栈顶元素）
     */
    public int[] asteroidCollision(int[] asteroids) {
        int n = asteroids.length;
        Deque<Integer> stack = new LinkedList<>();
        int p = 0;
        while (p < n) {
            if (stack.isEmpty() || stack.peek() < 0 || asteroids[p] > 0) {
                stack.push(asteroids[p]);
            }
            else if (stack.peek() <= -asteroids[p]) {
                if (stack.poll() < -asteroids[p]) continue;
            } 
            p++;
        }
        int[] res = new int[stack.size()];
        for (int i = stack.size()-1; i >= 0; --i) {
            res[i] = stack.poll();
        }
        return res;
    }
}