[数据结构与算法]剑指 Offer II 037. 小行星碰撞

题目

力扣

思路 栈

遍历行星，存到栈里面，如果栈不为空且栈顶元素向右，当前元素向左，就会发生碰撞。如果栈顶行星大小小于当前行星，就需要pop出来，并且需要添加当前元素入栈。如果栈顶行星大小等于当前行星，需要pop而且不push。如果栈顶行星大小大于当前行星，不pop也不push。用一个变量记录是否push就好了。

代码

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        stack<int> s;
        for(int a:asteroids){
            bool push=true;
            while(!s.empty() && s.top()>0 && a<0){
                if(s.top()<-a)
                    s.pop();
                else if(s.top()==-a){
                    push=false;
                    s.pop();
                    break;
                }else{
                    push=false;
                    break;
                }
            }
            if(push)
                s.push(a);
        }
        int n=s.size();
        vector<int> ans(n);
        for(int i=n-1;i>=0;i--){
            ans[i]=s.top();
            s.pop();
        }
        return ans;
    }
};