题目描述
给定一个整数数组 asteroids
,表示在同一行的行星。
对于数组中的每一个元素,其绝对值表示行星的大小,正负表示行星的移动方向(正表示向右移动,负表示向左移动)。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则:两个行星相互碰撞,较小的行星会爆炸。如果两颗行星大小相同,则两颗行星都会爆炸。两颗移动方向相同的行星,永远不会发生碰撞。
样例
输入:
asteroids = [5, 10, -5]
输出: [5, 10]
解释:
10 和 -5 碰撞后只剩下 10。 5 和 10 永远不会发生碰撞。
输入:
asteroids = [8, -8]
输出: []
解释:
8 和 -8 碰撞后,两者都发生爆炸。
输入:
asteroids = [10, 2, -5]
输出: [10]
解释:
2 和 -5 发生碰撞后剩下 -5。10 和 -5 发生碰撞后剩下 10。
输入:
asteroids = [-2, -1, 1, 2]
输出: [-2, -1, 1, 2]
解释:
-2 和 -1 向左移动,而 1 和 2 向右移动。
由于移动方向相同的行星不会发生碰撞,所以最终没有行星发生碰撞。
提示
- 数组
asteroids
的长度不超过10000
。 - 每一颗行星的大小都是非零整数,范围是
[-1000, 1000]
。
算法
(栈) $O(n)$
- 创建一个栈,初始为空,从头开始遍历数组。
- 如果遇到一个正数,则直接加入栈中。
- 如果遇到一个负数,则和栈顶比较绝对值,如果绝对值比栈顶要大,则栈顶出栈。直到栈空或者绝对值小于等于栈顶。此时如果栈空,则将这个数字放到答案数组中;如果栈不空且绝对值和栈顶元素相同,则栈顶再出栈。
- 遍历完成后,将栈中元素依次弹出,按相反顺序依次放入答案数组。
时间复杂度
- 每个数字仅遍历常数次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要额外的栈空间和存储答案的空间,故空间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
int n = asteroids.size();
stack<int> st;
vector<int> ans;
for (int aster: asteroids) {
if (aster < 0) {
while (!st.empty() && st.top() < -aster)
st.pop();
if (st.empty())
ans.push_back(aster);
else {
if (st.top() == -aster)
st.pop();
}
} else {
st.push(aster);
}
}
vector<int> t;
while (!st.empty()) {
t.push_back(st.top());
st.pop();
}
for (auto it = t.rbegin(); it != t.rend(); it++)
ans.push_back(*it);
return ans;
}
};