給定整數陣列
asteroids代表在同一列中的小行星。正數表示向右移動，負數表示向左移動，絕對值代表大小。兩個小行星相遇時，較小的會爆炸；若大小相同則同時爆炸。同方向的小行星永遠不會相遇。回傳碰撞後的狀態。
Example:
Input: asteroids = [5,10,-5] Output: [5,10]
Intuition
TIP
核心思路：用堆疊處理碰撞，只有「棧頂向右、新元素向左」時才會發生碰撞，反覆比較直到碰撞結束。
- 向右的小行星（正數）不會和之前向右的碰撞，直接入棧
- 向左的小行星（負數）會和之前向右的碰撞，需要逐一比較
- 碰撞結果有三種：新的爆炸、棧頂爆炸、同歸於盡
Approaches
1. Array as Stack (no boxing) — O(n) / O(n)
- Idea: 邏輯與堆疊解相同，改用
IntArray+ top 指標，避免ArrayDeque<Int>裝箱 - Time:
O(n)- 每顆小行星最多進出一次 - Space:
O(n)
class Solution {
fun asteroidCollision(asteroids: IntArray): IntArray {
val st = IntArray(asteroids.size)
var top = 0
for (a in asteroids) {
var alive = true
while (alive && a < 0 && top > 0 && st[top - 1] > 0) {
when {
st[top - 1] < -a -> top-- // 棧頂較小，爆炸
st[top - 1] == -a -> { top--; alive = false } // 同大同歸於盡
else -> alive = false // 棧頂較大，新的爆炸
}
}
if (alive) st[top++] = a
}
return st.copyOf(top)
}
}⭐ 2. Stack Simulating Collisions — O(n) / O(n)
- Idea: 遍歷小行星，正數直接 push。負數則與棧頂比較：棧頂較小就 pop 掉（繼續比較），棧頂較大就跳過新元素，一樣大就都移除
- Time:
O(n)- 每個小行星最多入棧出棧各一次 - Space:
O(n)
class Solution {
fun asteroidCollision(asteroids: IntArray): IntArray {
val stack = ArrayDeque<Int>()
for (ast in asteroids) {
var alive = true
while (alive && ast < 0 && stack.isNotEmpty() && stack.last() > 0) {
if (stack.last() < -ast) {
// 棧頂較小，爆炸
stack.removeLast()
} else if (stack.last() == -ast) {
// 同大，同歸於盡
stack.removeLast()
alive = false
} else {
// 棧頂較大，新的爆炸
alive = false
}
}
if (alive) {
stack.addLast(ast)
}
}
return stack.toIntArray()
}
}🔑 Takeaways
- Pattern: 元素之間有「衝突/消除」關係時，堆疊可以有效模擬
- Key trick: 用布林變數
alive追蹤新元素是否存活，清晰地處理三種碰撞結果。注意碰撞條件：只有「棧頂 > 0 且新元素 < 0」才會碰撞