题目描述

给定一个整数数组 asteroids，表示在同一行的行星。

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

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

样例

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

算法1

(栈模拟) $O(n^2)$

这个题目用栈模拟一下这整个过程就好了，大部分代码都写了注释，大家如果有哪些地方看不懂，也欢迎留言讨论。

C++ 代码

vector<int> asteroidCollision(vector<int>& as) {
        vector<int> ans;
        stack<int> stk;

        int m = as.size();

        for (int i = 0; i < m; ++ i) 
        {
            //当栈为空并且一个左移星球来的时候 没人能把我撞下来吧 那我就记入答案咯
            if (stk.empty() && as[i] < 0) ans.push_back(as[i]);
            //把所有的右移星球都放到栈内 用栈是为了保证最有可能碰撞的星球最先出来 
            if (as[i] > 0) stk.push(as[i]);

            if (!stk.empty() && as[i] < 0)
            {
                //这个左移星球把所有比他小的右移星球全吃了
                while (!stk.empty() && abs(as[i]) > stk.top()) stk.pop();
                //右移星球都被我吃了 那我是这片区域的老大了吧 所以 我记入答案
                if (stk.empty()) ans.push_back(as[i]);
                //别忘了把第一个和左移星球相等的右移星球 去掉哦
                if (!stk.empty() && abs(as[i]) == stk.top()) stk.pop();
            }
        }

        //后面就是把还活着的右移星球输出来了
        ans.resize(ans.size() + stk.size());  
        int n = ans.size();

        while (!stk.empty())
        {   
            //cout<<stk.top();
            ans[n-1] = stk.top();
            stk.pop();
            --n;
        }

        return ans;
    }