LeetCode 735. 行星碰撞

LeetCode 735. 行星碰撞
思路：

实际就是模拟了栈的过程。
当前元素大于0，放入答案里面，
当前元素小于0，与答案末尾比较，如果绝对值大于答案末尾，末尾弹出，如果两个元素相同，则答案末尾弹出，当前元素不做处理，如果答案末尾是小于0的，说明两个行星永远不会碰撞，放入答案里面。

代码：

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> res;
        for(auto x : asteroids){
            if(x > 0) res.push_back(x);
            else{
                while(res.size() && res.back() > 0 && res.back() < -x) res.pop_back();
                if(res.size() && res.back() == -x) res.pop_back();
                else if(!res.size() || res.back() < 0) res.push_back(x);
            }
        }
        return res;
    }
};

栈

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        stack<int> stk;
        for(auto x : asteroids){
            if(x > 0) stk.push(x);
            else{
                while(stk.size() && stk.top() > 0 && stk.top() < -x) stk.pop();
                if(stk.empty() || stk.top() < 0) stk.push(x);
                else if(stk.size() && stk.top() == -x) stk.pop();
            }
        }
        vector<int> res;
        while(stk.size()) {
            res.push_back(stk.top());
            stk.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
``