735. 小行星碰撞

🟠   🔖  栈 数组 模拟  🔗 力扣 LeetCode

题目

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]

Output: [5,10]

Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]

Output: []

Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]

Output: [10]

Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Constraints:

• 2 <= asteroids.length <= 10^4
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

题目大意

给定一个整数数组 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 <= asteroids.length <= 10^4
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

解题思路

可以使用栈来模拟小行星碰撞的过程，遍历每个小行星时，通过栈来保存未发生碰撞的小行星。

1. 遍历数组中的每个小行星，last 表示栈顶元素（上一个小行星），cur 表示当前遍历的小行星。
2. 不同情况处理：
   • 栈为空 或 栈顶元素方向向左 (last < 0) 或 当前小行星向右 (cur > 0) 时，将当前小行星直接入栈，因为此时不会发生碰撞。
   • 大小相等时 (last + cur == 0)：两个小行星相互抵消，将栈顶元素弹出，不将当前小行星入栈。
   • 栈顶小行星较小（即 last + cur < 0）：此时，栈顶小行星被消灭，弹出栈顶元素并重新检查当前小行星。通过将 i 减 1，确保下一次循环仍然处理当前小行星 cur，使其继续与栈内前一个小行星发生碰撞。
3. 返回结果：栈中剩余的小行星就是不会被消灭的小行星。

复杂度分析

• 时间复杂度：O(n)，每个小行星最多入栈和出栈一次。
• 空间复杂度：O(n)，栈的最大深度为 n。

代码

/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function (asteroids) {
	let stack = [];
	for (let i = 0; i < asteroids.length; i++) {
		const last = stack[stack.length - 1];
		const cur = asteroids[i];

		if (!stack.length || last < 0 || cur > 0) {
			// 栈为空 或 栈顶小行星向左 或 当前小行星向右，直接入栈
			stack.push(cur);
		} else if (last + cur == 0) {
			// 栈顶和当前小行星相同大小且相反方向，互相抵消
			stack.pop();
		} else if (last + cur < 0) {
			// 栈顶小行星较小，被当前小行星消灭，弹出栈顶并重新比较新的栈顶和当前小行星
			stack.pop();
			i--;
		}
	}
	return stack;
};

相关题目

题号	标题	题解	标签	难度	力扣
605	种花问题	[✓]	贪心 数组	🟢	🀄️ 🔗
2126	摧毁小行星		贪心 数组 排序	🟠	🀄️ 🔗
2211	统计道路上的碰撞次数		栈 字符串 模拟	🟠	🀄️ 🔗
2751	机器人碰撞		栈 数组 排序 1+	🔴	🀄️ 🔗