题目描述

blablabla

样例

blablabla

$O(n)$

C++ 代码

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

        for (auto i : asteroids){

            if (S.empty()){
                if (i < 0){
                    result.push_back(i);
                }
                else{
                    S.push(i);
                }
                continue;
            }

            if (i > 0){
                S.push(i);
                continue;
            }

            int flag = 0;

            while(!S.empty()){
                int prev = S.top();

                if (prev > -i){
                    break;
                }

                else if (prev == -i){
                    S.pop();
                    flag = 1;
                    break;
                }
                else {
                    S.pop();
                }
            }

            if (S.empty() && flag == 0){
                result.push_back(i);
            }

        }
        vector<int> result2;

        while(!S.empty()){
            result2.push_back(S.top());
            S.pop();
        }
        reverse(result2.begin(), result2.end());

        for (auto i : result2){
            result.push_back(i);
        }
        return result; 
    }
};