LeetCode 735: Asteroid Collision (Stack Simulation of Right-Moving Survivors)
LeetCode 735StackSimulationToday we solve LeetCode 735 - Asteroid Collision.
Source: https://leetcode.com/problems/asteroid-collision/
English
Problem Summary
Each asteroid has a size and direction (positive = right, negative = left). Asteroids moving in the same direction never meet. When a right-moving asteroid meets a left-moving one, the smaller explodes; equal sizes both explode. Return the final surviving sequence.
Key Insight
Potential collisions only happen when a new asteroid goes left (< 0) and the current survivor tail goes right (> 0). A stack naturally stores current survivors, and we resolve collisions against the top until the new asteroid is destroyed or safely appended.
Optimal Algorithm Steps
1) Iterate asteroids one by one.
2) If current asteroid goes right, push directly.
3) If it goes left, while stack top is right-moving, compare absolute sizes and resolve collisions.
4) Push current asteroid only if it survives all collisions.
5) Convert stack to result array.
Complexity Analysis
Time: O(n), because each asteroid is pushed/popped at most once.
Space: O(n) in the worst case.
Common Pitfalls
- Forgetting to keep colliding in a loop for one strong left-moving asteroid.
- Handling only one collision and immediately pushing.
- Wrong equal-size rule (both must explode).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Deque<Integer> stack = new ArrayDeque<>();
for (int a : asteroids) {
boolean alive = true;
while (alive && a < 0 && !stack.isEmpty() && stack.peekLast() > 0) {
int top = stack.peekLast();
if (top < -a) {
stack.pollLast();
} else if (top == -a) {
stack.pollLast();
alive = false;
} else {
alive = false;
}
}
if (alive) stack.offerLast(a);
}
int[] ans = new int[stack.size()];
int i = 0;
for (int v : stack) ans[i++] = v;
return ans;
}
}func asteroidCollision(asteroids []int) []int {
stack := make([]int, 0)
for _, a := range asteroids {
alive := true
for alive && a < 0 && len(stack) > 0 && stack[len(stack)-1] > 0 {
top := stack[len(stack)-1]
if top < -a {
stack = stack[:len(stack)-1]
} else if top == -a {
stack = stack[:len(stack)-1]
alive = false
} else {
alive = false
}
}
if alive {
stack = append(stack, a)
}
}
return stack
}class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> st;
for (int a : asteroids) {
bool alive = true;
while (alive && a < 0 && !st.empty() && st.back() > 0) {
int top = st.back();
if (top < -a) {
st.pop_back();
} else if (top == -a) {
st.pop_back();
alive = false;
} else {
alive = false;
}
}
if (alive) st.push_back(a);
}
return st;
}
};class Solution:
def asteroidCollision(self, asteroids: list[int]) -> list[int]:
stack = []
for a in asteroids:
alive = True
while alive and a < 0 and stack and stack[-1] > 0:
top = stack[-1]
if top < -a:
stack.pop()
elif top == -a:
stack.pop()
alive = False
else:
alive = False
if alive:
stack.append(a)
return stackvar asteroidCollision = function(asteroids) {
const stack = [];
for (const a of asteroids) {
let alive = true;
while (alive && a < 0 && stack.length && stack[stack.length - 1] > 0) {
const top = stack[stack.length - 1];
if (top < -a) {
stack.pop();
} else if (top === -a) {
stack.pop();
alive = false;
} else {
alive = false;
}
}
if (alive) stack.push(a);
}
return stack;
};中文
题目概述
每个小行星的绝对值是大小，正负号是方向（正向右，负向左）。同向不会相撞；当右行与左行相遇时，小的爆炸，相等则同归于尽。返回最终剩余序列。
核心思路
只有“栈顶向右 + 当前向左”才会发生碰撞，所以用栈维护当前幸存序列最自然。对一个向左的小行星，需要持续与栈顶比较，直到它被摧毁或成功存活。
最优算法步骤
1）遍历输入数组。
2）当前值向右时直接入栈。
3）当前值向左时，只要栈顶向右就循环碰撞比较绝对值。
4）若当前值存活，入栈。
5）最后把栈转为答案数组。
复杂度分析
时间复杂度：O(n)，每个元素最多入栈出栈一次。
空间复杂度：O(n)。
常见陷阱
- 忘了用 while 连续处理多次碰撞。
- 只处理一次就把当前元素入栈，导致错误。
- 相等大小时没有同时移除两者。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Deque<Integer> stack = new ArrayDeque<>();
for (int a : asteroids) {
boolean alive = true;
while (alive && a < 0 && !stack.isEmpty() && stack.peekLast() > 0) {
int top = stack.peekLast();
if (top < -a) {
stack.pollLast();
} else if (top == -a) {
stack.pollLast();
alive = false;
} else {
alive = false;
}
}
if (alive) stack.offerLast(a);
}
int[] ans = new int[stack.size()];
int i = 0;
for (int v : stack) ans[i++] = v;
return ans;
}
}func asteroidCollision(asteroids []int) []int {
stack := make([]int, 0)
for _, a := range asteroids {
alive := true
for alive && a < 0 && len(stack) > 0 && stack[len(stack)-1] > 0 {
top := stack[len(stack)-1]
if top < -a {
stack = stack[:len(stack)-1]
} else if top == -a {
stack = stack[:len(stack)-1]
alive = false
} else {
alive = false
}
}
if alive {
stack = append(stack, a)
}
}
return stack
}class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> st;
for (int a : asteroids) {
bool alive = true;
while (alive && a < 0 && !st.empty() && st.back() > 0) {
int top = st.back();
if (top < -a) {
st.pop_back();
} else if (top == -a) {
st.pop_back();
alive = false;
} else {
alive = false;
}
}
if (alive) st.push_back(a);
}
return st;
}
};class Solution:
def asteroidCollision(self, asteroids: list[int]) -> list[int]:
stack = []
for a in asteroids:
alive = True
while alive and a < 0 and stack and stack[-1] > 0:
top = stack[-1]
if top < -a:
stack.pop()
elif top == -a:
stack.pop()
alive = False
else:
alive = False
if alive:
stack.append(a)
return stackvar asteroidCollision = function(asteroids) {
const stack = [];
for (const a of asteroids) {
let alive = true;
while (alive && a < 0 && stack.length && stack[stack.length - 1] > 0) {
const top = stack[stack.length - 1];
if (top < -a) {
stack.pop();
} else if (top === -a) {
stack.pop();
alive = false;
} else {
alive = false;
}
}
if (alive) stack.push(a);
}
return stack;
};
Comments