735. Asteroid Collision
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign
represents its direction (positive meaning right, negative meaning left). Each
asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids
meet, the smaller one will explode. If both are the same size, both will
explode. Two asteroids moving in the same direction will never meet.
小行星有体积(数字大小)跟飞行方向(正负号)，飞行方向相撞会比大小决定谁留着。
Example 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Example 2:
Input: asteroids = [8,-8]
Output: []
Example 3:
Input: asteroids = [10,2,-5]
Output: [10]
Step:
用Stack解比较方便
题目说明可以看这个：https://www.youtube.com/watch?v=LN7KjRszjk4
建立Stack
│
for遍历小行星阵列
│
└── while判断是否碰撞
│ ├─ 条件1: Stack不为空
│ ├─ 条件2: 左小行星向右移动
│ ├─ 条件3: 右小行星向左移动
│ │
│ 发生碰撞的处理
│ ├─ 右边小行星较大
│ │ └─ 左小行星毁损，从Stack把左小行星移除
│ ├─ 左边小行星较大
│ │ └─ 右小行星损毁，大小设为0
│ ├─ 一样大
│ │ └─ 两颗都毁损，从Stack移除左，右大小设为0
│ │
│ 如果判断结束右小行星还在
│ └─ 加入Stack，跑下一轮while
│
└─ 最后记得把Stack转回Vector以return
Code:
没Rust 明天再写
class Solution
{
public:
vector<int> asteroidCollision(vector<int>& asteroids)
{
stack<int> result;
for (int i = 0; i < asteroids.size(); i++)
{
int right_asteroid = asteroids[i];
while (!result.empty() &&
result.top() > 0 &&
right_asteroid < 0)
{
int left_asteroid = result.top();
if (left_asteroid < -right_asteroid)
{
result.pop();
}
else if (left_asteroid == -right_asteroid)
{
result.pop();
right_asteroid = 0;
}
else
{
right_asteroid = 0;
break;
}
}
if (right_asteroid)
result.push(right_asteroid);
}
vector<int> output(result.size());
for(int i = result.size() - 1; i >= 0; i