题目
给定一个整数数组 asteroids，表示在同一行的行星。
对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
示例 1：
输入：asteroids = [5,10,-5] 输出：[5,10] 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
示例 2：
输入：asteroids = [8,-8] 输出：[] 解释：8 和 -8 碰撞后，两者都发生爆炸。
示例 3：
输入：asteroids = [10,2,-5] 输出：[10] 解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
解题
方法一：栈模拟
class Solution { public: vector<int> asteroidCollision(vector<int>& asteroids) { deque<int> st; for(int num:asteroids){ st.push_back(num); while(st.size()>=2){ int last=st[st.size()-1]; int pre=st[st.size()-2]; if(last*pre>0||pre<0||last>0) break; if(abs(last)==abs(pre)){ st.pop_back(); st.pop_back(); }else if(abs(pre)>abs(last)){ st.pop_back(); } else{ st.pop_back(); st.pop_back(); st.push_back(last); } } } return vector<int>(st.begin(),st.end()); } };
方法二：数组模拟栈
class Solution { public: vector<int> asteroidCollision(vector<int>& asteroids) { int l=asteroids.size(); vector<int> arr(l); int p=-1; for(int a:asteroids){ bool ok=true; while(p!=-1&&ok&&a<0&&arr[p]>0){ ok=-a>arr[p]; if(-a>=arr[p]){ p--; } } if(ok) arr[++p]=a; } return vector<int>(arr.begin(),arr.begin()+p+1); } };
