735.小行星碰撞

链接：735.小行星碰撞
难度：Medium
标签：栈、数组、模拟
简介：找出碰撞后剩下的所有行星。

题解 1 - cpp

• 编辑时间：2022-07-13
• 执行用时：16ms
• 内存消耗：17.3MB
• 编程语言：cpp
• 解法介绍：栈。

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