https://leetcode.com/contest/weekly-contest-60/problems/asteroid-collision/

#include <deque>
#include <vector>
#include <stdio.h>
#include <stdlib.h> 

using namespace std;

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        std::deque<int> s;
        vector<int> ans;
        for (int i = 0; i < asteroids.size(); i++) {
            if (asteroids[i] > 0) {
                s.push_back(asteroids[i]);
            } else {
                int now = -1 * asteroids[i];
                while (1) {
                    if (s.empty()) {
                        ans.push_back(asteroids[i]);
                        break;
                    }
                    int other = s.back();
                    if (other <= now) {
                        s.pop_back();
                        if (other == now) {
                            break;
                        }
                    } else {
                        break;
                    }
                }
            }
        }
        while (!s.empty()) {
            ans.push_back(s.front());
            s.pop_front();
        }
        return ans;
    }
};

int main()
{
    int inArray[] = {-2, -1, 1, 2};
    vector<int> in(inArray, inArray + sizeof(inArray)/sizeof(int));
    vector<int> ans;
    Solution s;
    for (int i = 0; i < in.size(); i++) {
        printf("%d\n", in[i]);
    }
    ans = s.asteroidCollision(in);
    for (int i = 0; i < ans.size(); i++) {
        printf("%d\n", ans[i]);
    }
    system("pause");
}