题目
概述：给定一个数组，代表移动速度相同的行星，数组元素的绝对值表示行星的大小，正负代表行星的移动方向（左负右正），移动方向不同的行星会发生碰撞，小的行星遇到大的行星会爆炸，大小相同的行星相遇都会爆炸，问最后剩下哪些行星
输入：行星数组，长度范围[0, 10000]
输入子项：非零整数，大小范围[-1000, 1000]
输出：碰撞后最终剩下的行星数组
思路
由于需要记录之前的行星信息用来判断是否会发生碰撞，所以考虑用栈实现
-
遍历行星数组：
- 正数 => 直接入栈
- 负数：
- 栈为空 => 直接入栈
- 栈顶元素为负数 => 直接入栈
- 栈顶元素为正数：
- 当前元素绝对值 == 栈顶元素绝对值 => 栈顶元素出栈
- 当前元素绝对值 > 栈顶元素绝对值 => 栈顶元素出栈，重复
栈中所剩元素即为碰撞后最终剩下的行星
代码
class Solution {
public int[] asteroidCollision(int[] asteroids) {
LinkedList<Integer> stack = new LinkedList<>();
for (int i = 0; i < asteroids.length; ++i) {
if (asteroids[i] > 0) {
stack.push(asteroids[i]);
} else {
while (true) {
if (stack.isEmpty() || stack.peek() < 0) {
stack.push(asteroids[i]);
break;
} else {
if (asteroids[i] + stack.peek() == 0) {
stack.pop();
break;
} else if (asteroids[i] + stack.peek() < 0) {
stack.pop();
} else {
break;
}
}
}
}
}
int[] result = new int[stack.size()];
for (int i = stack.size() - 1; i >= 0; --i) {
result[i] = stack.pop();
}
return result;
}
}
