LeetCode 735. 小行星碰撞
题目描述
题意分析
数组顺序表示小行星从左到右的位置，正数向右、负数向左，绝对值表示大小。相撞时较小者消失，一样大则双方消失，幸存者的大小和方向不变。所有小行星速度相同，因此同向的不会追上，左负右正的会远离，只有左正右负可能相撞。
解法：栈模拟连续碰撞
核心思路
[!blue]
从左到右扫描，用栈保存已处理前缀的幸存者，栈底到栈顶保持原位置顺序，并保证前缀内部的碰撞已处理完。新行星位于这些幸存者的右侧；若有碰撞，必然先遇到离它最近的栈顶，所以只需要从栈顶开始判断。
只有当前
asteroid < 0且栈顶top > 0时，两者才相向移动。比较top与-asteroid：栈顶较小就弹出，当前行星继续与新的栈顶碰撞；相等就弹出栈顶并令当前行星死亡；栈顶较大则只令当前行星死亡。alive用来记录当前行星是否还存在，死亡后不能继续碰撞或入栈。当前行星仍存活时，若栈空或栈顶与它不再相向，就可以入栈，已处理前缀又恢复到没有待发生碰撞的状态。每轮碰撞要么永久弹出一个栈顶，要么结束当前行星的处理，不会反复扫描已经消失的行星。
解题步骤
- 初始化空栈，依次读取每颗小行星
asteroid，先标记它仍存活。- 当当前值为负、栈顶为正且当前仍存活时，进入碰撞循环。
- 栈顶更小时弹栈并继续；相等时弹栈且让当前值消失；栈顶更大时只让当前值消失。
- 碰撞循环结束后，若当前值仍存活，就把它压栈。
- 扫描完成后，栈中元素就是最终结果，顺序无需反转。
代码实现
class Solution {
public int[] asteroidCollision(int[] asteroids) {
int[] stack = new int[asteroids.length];
int size = 0;
for (int asteroid : asteroids) {
boolean alive = true;
// 只有左侧向右、当前向左时会相撞，存活者可能继续向左碰撞。
while (alive && asteroid < 0 && size > 0 && stack[size - 1] > 0) {
int top = stack[size - 1];
if (top < -asteroid) {
size--;
} else if (top == -asteroid) {
size--;
alive = false;
} else {
alive = false;
}
}
// 当前行星未被更大或等大的栈顶消灭时，才可加入结果。
if (alive) {
stack[size++] = asteroid;
}
}
return Arrays.copyOf(stack, size);
}
}
func asteroidCollision(asteroids []int) []int {
stack := make([]int, 0, len(asteroids))
for _, asteroid := range asteroids {
alive := true
// 只有左侧向右、当前向左时会相撞，存活者可能继续向左碰撞。
for alive && asteroid < 0 && len(stack) > 0 && stack[len(stack)-1] > 0 {
top := stack[len(stack)-1]
if top < -asteroid {
stack = stack[:len(stack)-1]
} else if top == -asteroid {
stack = stack[:len(stack)-1]
alive = false
} else {
alive = false
}
}
// 当前行星未被更大或等大的栈顶消灭时，才可加入结果。
if alive {
stack = append(stack, asteroid)
}
}
return stack
}
复杂度分析
- 时间复杂度：$O(n)$。每颗小行星最多入栈、出栈各一次；不弹栈的碰撞会使当前行星死亡，每颗也至多发生一次，因此所有碰撞操作合计为线性次数。
- 空间复杂度：$O(n)$。最坏情况下没有碰撞，栈保存全部小行星。
关键点总结
[!green]
- 是否碰撞取决于相邻幸存者的方向：只有「正数在左、负数在右」需要处理。
- 当前负数可能连续撞碎多个较小的正数，因此必须使用
while。- 三种大小关系要完整区分；相等时双方都消失。
- 栈始终保存已处理前缀的最终幸存者，返回时保持原顺序，不需要反转。
易错点总结
[!yellow]
- 判断符号相反还不够，必须是栈顶为正、当前为负；顺序相反时两者正在远离。
- 当前行星撞碎较小栈顶后仍然存活，必须继续循环；相等时则既要弹栈，也要把
alive设为false。- 只能在
alive为真时入栈，否则会把已经消失的当前行星重新放回结果。- Java 的定长数组只有
[0, size)有效，需截取这个前缀；从栈底到栈顶已是答案顺序，不应反转。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1047. 删除字符串中的所有相邻重复项 | 简单 | 同样用栈保存仍存活的前缀，新元素可能触发连续消除，本题需额外判断方向和绝对值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！