首先要明确一点:只有一种情况会导致小行星发生碰撞,那就是当前小行星往左飞行,而上一个小行星往右飞行时。
思路:
-
遍历小行星数组,遇到往右飞行的小行星直接入栈,因为假设速度相同,往右飞的行星都不会发生碰撞;
-
当遇到往左飞的小行星时,表示可能会发生碰撞,这时循环判断栈顶小行星是否大于当前小行星,比当前小行星小的全都原地爆炸,直到遇到比当前小行星大的把当前小行星撞碎为止,或者栈空为止;
-
这里还需要额外判断两颗相撞小行星大小相等的情况,会同时爆炸;
-
最后栈中剩余的小行星就是永远不会发生碰撞的小行星。
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> res; //我们用数组模拟栈
for (int &item : asteroids) //遍历小行星
{
//栈不为空,栈顶小行星向右飞行,当前小行星向左飞行且栈顶小行星较小的情况,栈顶小行星爆炸
while (!res.empty() && res.back() > 0 && res.back() < -item)
{
res.pop_back();
}
//栈不为空,当前小行星向左飞行,且俩行星大小相同的情况,同时爆炸
if (!res.empty() && item < 0 && res.back() == -item)
{
res.pop_back();
}
//1、若当前小行星向右飞行,不用管栈顶小行星的飞行方向,它肯定不会与栈顶小行星相撞;
//2、栈为空时,当前小行星入栈;
//3、若栈顶小行星向左飞行,不用管当前小行星的飞行方向,它肯定不会与栈顶小行星相撞;
else if (item > 0 || res.empty() || res.back() < 0)
{
res.push_back(item);
}
}
return res;
}
};