Description

Submission 1

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        stack<int> stk;


        for (auto x: asteroids) {
            if (stk.empty() || stk.top() < 0 || (stk.top() > 0 && x > 0)) {
                stk.push(x);
                continue;
            }

            while (!stk.empty()) {
                
                auto y = stk.top(); // 1
                if (y < 0 || (y > 0 && x > 0)) break; // y = 1, x = -2
                // y > 0 && x < 0
                if (y == -x) {
                    stk.pop();
                    break;
                }

                if (y < -x) {
                    stk.pop();
                    if (stk.empty() || stk.top() < 0)
                        stk.push(x);
                    continue;
                }

                if (y > -x) {
                    break;
                }
            }
        }

        vector<int> rets;

        while(!stk.empty()) {
            rets.push_back(stk.top());
            stk.pop();
        }

        reverse(rets.begin(), rets.end());

        return rets;
    }
};

// -2 -2 1 -2

Submission 2

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        set<int> goRight;
        set<int> goLeft;

        for(size_t i = 0; i < asteroids.size(); ++i) {
            if(asteroids[i] > 0) {
                goRight.insert(i);
            } else {
                goLeft.insert(i);
            }
        }

        int prevRightCnt = goRight.size(), prevLeftCnt = goLeft.size();
        while(true) {
            
            for(auto iterRight = goRight.begin(); iterRight != goRight.end(); ++iterRight) {
                auto iterLeft = goLeft.upper_bound(*iterRight);
                if (iterLeft == goLeft.end()) continue;
                if (next(iterRight) != goRight.end() && 
                    *next(iterRight) < *(iterLeft)) continue;
                auto x = *iterRight;
                auto y = *iterLeft;
                if (asteroids[x] <= -asteroids[y]) {
                    goRight.erase(x);
                }
                if (asteroids[x] >= -asteroids[y]) {
                    goLeft.erase(iterLeft);
                }
                break;
            }
        
            if (prevLeftCnt == goLeft.size() && prevRightCnt == goRight.size()) break;
            prevRightCnt = goRight.size();
            prevLeftCnt = goLeft.size();
        }

        vector<int> rets;

        goRight.insert(goLeft.begin(), goLeft.end());

        for(auto idx: goRight) {
            rets.push_back(asteroids[idx]);
        }

        return rets;
        
    }
};

// 1 1 -1

// 1 -1 -1 1 1 1 1 -1 1 1 1 -1 -1 -1 [1 1]

// goLeft 2
// goRight 0 1


// goLeft 0 1
// goRight 2