教育网站报名上海网站设计
1.题目描述
735. 行星碰撞
给定一个整数数组 asteroids，表示在同一行的行星。
对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
示例 1：
输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
示例 2：
输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。
示例 3：
输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
2.解题思路与代码
2.1 解题思路
题目说正数行星向右运动，负数行星向左运动，那么当数组中遇到负数时，就需要与该数前面的正数进行比较，如果前面是正数，那么发生碰撞留下绝对值较大的；绝对值相等则抵消，两数消失。根据这一思路，使用栈进行解答。遍历数组如果当前数大于 0 ，并且栈顶元素小于 0，那么就需要弹出栈顶元素与当前数进行比较，就会有以下三种情况：
- 如果当前元素绝对值大于弹出元素绝对值，选择当前元素，继续弹出栈顶元素进行比较；
- 如果当前元素绝对值小于弹出元素绝对值，选择弹出元素并退出循环，弹出元素重新入栈
- 如果当前元素绝对值等于弹出元素绝对值，两数同时消失
下面用题目示例 [5, 10, -5] 进行图解：
-
首先 index=0 指向 5，此时栈为空直接入栈
-
index 右移，此时 index 指向元素和栈顶元素都大于 0，方向相同不会碰撞直接入栈
-
index 右移，此时 index 指向 -5，栈顶元素为 10，会发生碰撞因此弹出栈顶 10 与 -5 进行比较，10 的绝对值大于 -5 的绝对值，因此 -5 消失留下 10。循环这一步，当前元素为 10 栈顶为 5 不会发生碰撞，10 重新入栈
-
数组遍历完成，最后栈中留下 5 和 10 位最终答案
由于答案需要返回一个数组，为了便于最终将结果转数组因此代码中使用数组模拟栈，同样也可以使用双端队列来做。
2.2 代码
class Solution {public int[] asteroidCollision(int[] asteroids) {// 为便于返回结果数组，使用数组模拟栈int[] stack = new int[asteroids.length];int idx = -1;// 开始时将数组第一个元素入栈stack[++idx] = asteroids[0];int index = 1;while (index < asteroids.length) {Integer chooseNum = asteroids[index];// 当选择数字小于 0，栈顶数字大于 0 时会发生碰撞，需要进行处理while (idx > -1 && chooseNum < 0 && stack[idx] > 0) {// 弹出栈顶数字Integer pop = stack[idx--];if (Math.abs(chooseNum) > pop) {// 如果选择的数绝对值大于弹出栈的数绝对值，则保留选择的数，继续循环continue;} else if (Math.abs(chooseNum) < pop) {// 如果选择的数绝对值小于弹出栈的数绝对值，选择数字改为弹出的数字// 下次循环条件判断不通过，退出循环后直接重新入栈chooseNum = pop;} else {// 如果选择的数绝对值等于弹出栈的数绝对值，两数同时消失，chooseNum 置 nullchooseNum = null;break;}}if (chooseNum != null) {stack[++idx] = chooseNum;}index++;}int[] ans = new int[idx + 1];System.arraycopy(stack, 0, ans, 0, idx + 1);return ans;}
}
2.3 测试结果
通过测试
3.总结
- 使用栈进行解答
- 当元素大于 0，栈顶元素小于 0 时会发生碰撞，此时需要处理
- 处理时比较当前元素和弹出栈元素的绝对值大小，绝对值大的保留，并循环比较保留数和栈顶元素的情况