C++ simple and fast solution beats 91.5%!


  • 0
    M

    Well, this solution is much faster than using vector to simulate stack :)

        vector<int> asteroidCollision(vector<int>& asteroids) {
            vector<int> res;
            stack<int> stk;
            for(int i=0;i<asteroids.size();i++) {
                if(asteroids[i]<0) {
                    while(!stk.empty()&&stk.top()>=0&&stk.top()+asteroids[i]<0) stk.pop();
                    if(stk.empty()||stk.top()<0) stk.push(asteroids[i]);
                    else if(stk.top()+asteroids[i]==0) stk.pop();
                }
                else stk.push(asteroids[i]);
            }
            while(!stk.empty()) {
                res.push_back(stk.top());
                stk.pop();
            }
            reverse(res.begin(), res.end());
            return res;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.