LeetCode | 735. 行星碰撞
题目描述
题目直接从 LeetCode 上截图过来，题目如下：
题目是一道有方向的比大小的问题。且是一道循环消除的问题。题目中给出了 4 组测试用例，也基本上把本题的所有可能的情况都覆盖了。这道题看似使用数组即可完成，但是它有循环消除的情况在里面，因此用栈来做更为方便。
本题我使用 Java 语言来完成，LeetCode 给出的 Java 定义如下：
class Solution {
public int[] asteroidCollision(int[] asteroids) {
}
}题目分析
题目中说明会给出一个数组，数组中的元素的绝对值是该星球的大小，这里需要注意是绝对值，而不是数值本身。星球有移动的方向，正数表示向右移动，负数表示向左移动。这是基本的情况。
碰撞的规则是，两个星球相遇，则小的会爆炸；如果两个星球相同大小，则都会爆炸。如果两个星球同方向则不会碰撞。
具体来举例看看。
我们使用题目中给出的第三个测试用例，[10, 2, -5] 来进行演示。初始化时如下图。
第一个数值 10，按照题目中给出的，它是向右移动，且栈中为空，那么 10 直接进栈，如下图。
接着第二个数值是 2，同样数值 2 是向右移动，虽然栈中不为空，但是 2 和栈顶的 10 是相同方向的，不会产生碰撞，那么 2 进入栈顶，如下图。
接着下一个数值为 -5，按照题目它是向左侧移动的，它和栈顶的 2 会相撞，因为 2 是向右移动，-5 是向左移动。它们相撞时，因为 -5 的绝对值大于 2，那么 2 则会爆炸，将其出栈，如下图。
此时，-5 需要再次和栈顶的 10 进行相遇，同样狭路相逢数值小的挂，那么 -5 炸了。由于数组中在 -5 后面没有数值，那么整个数组只剩 [10] 了。
通过我们的模拟，得到的结果与题目中给出的测试用例是相同的。
代码实现
看一下我写的 Java 代码，代码如下。
class Solution {
public int[] asteroidCollision(int[] asteroids) {
// 长度小于等于1个，直接返回
// 没有碰撞的机会
final int number = asteroids.length;
if (number <= 1) {
return asteroids;
}
// 左移和右移
final int left = 0;
final int right = 1;
Stack<Integer> t = new Stack();
for (int i = 0; i < number; i ++) {
// 当前星球往哪边移动
final int curDirection = asteroids[i] >= 0 ? right : left;
// 当前星球的大小
final int curSize = Math.abs(asteroids[i]);
// 是否炸了
boolean boom = false;
while (!t.empty() // 栈不为空
&& (t.peek() >= 0 ? right : left) == right // 栈顶星球是否向右
&& curDirection == left) { // 当前星球是否香左
// 相同就碰撞，且栈顶的也出栈
if (t.peek() == curSize) {
boom = true;
t.pop();
break;
}
// 栈顶的比当前的星球大，则当前星球被撞
// 且跳出循环
if (t.peek() > curSize) {
boom = true;
break;
}
// 上面两个条件都不满足
// 则说明当前的比栈顶的星球大
// 栈顶的星球出栈
t.pop();
}
// 如果当前的星球没炸
// 则进入栈顶
if (!boom) {
t.push(asteroids[i]);
}
}
// 通过栈来构造剩下星球的数组
int[] arr = new int[t.size()];
for (int i = t.size() - 1;i >= 0; i --) {
arr[i] = t.peek();
t.pop();
}
return arr;
}
}解释一下代码。
1、如果 asteroids 的长度小于等于 1，那么就说明没有相撞的可能性，直接返回；
2、依次遍历数组，在满足 栈顶元素向右移动 且 当前元素向左移动 时，用当前的值来循环和栈中的数值进行比对；
3、比较时，大的留下，小的爆炸，也就是大的要进栈；如果相等则同时爆炸；
4、将栈中留下的元素出栈，并放入一个数组中，进行返回。
提交结果
在写完 asteroidCollision 方法体后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们继续修改代码。
