題目
#

leetcode 735 - Asteroid Collision (題目說明請點連結)

題目簡述
#

給定一個整數陣列 asteroids，表示行星的大小和方向。正值表示向右移動，負值表示向左移動。當行星相遇時會發生碰撞，較小的行星會被摧毀。返回碰撞後剩餘的行星。

範例
#

Example 1:

Input: asteroids = [5, 10, -5]
Output: [5, 10]
Explanation: 行星 -5 與 10 碰撞並被摧毀。

Example 2:

Input: asteroids = [8, -8]
Output: []
Explanation: 行星 8 與 -8 碰撞，兩者都被摧毀。

Example 3:

Input: asteroids = [10, 2, -5]
Output: [10]
Explanation: 行星 -5 與 2 碰撞並摧毀它，然後與 10 碰撞並被摧毀。

解題思路
#

這題要求模擬行星碰撞的過程，規則如下：

每顆行星的值代表其大小與方向：
- 正值表示向右移動。
- 負值表示向左移動。
當行星相遇時：
- 若方向相同，則繼續前進。
- 若相對方向，則發生碰撞，較小的行星被摧毀。
- 若兩顆行星大小相等，則都被摧毀。
需要維護行星的最終狀態。

使用 Stack（堆疊） 來解決這個問題：

依序遍歷 asteroids 陣列，將行星推入堆疊。
若遇到負值行星，則檢查堆疊頂端是否為正值行星，並進行碰撞處理。
持續彈出較小的行星，直到找到適當的位置。
最後返回堆疊中的行星作為結果。

例子說明
#

asteroids = [10, 2, -5]

初始情況：stack = []

處理第一個行星 10：
- 正值，直接推入堆疊，stack = [10]
處理第二個行星 2：
- 正值，直接推入堆疊，stack = [10, 2]
處理第三個行星 -5：
- 負值，檢查堆疊頂端 2
- |-5| = 5 > 2，彈出 2，stack = [10]
- 繼續檢查堆疊頂端 10
- |-5| = 5 < 10，不彈出，stack = [10]
- 最終 stack = [10]
最終結果：
- 返回 [10]

完整程式碼
#

java

import java.util.Stack;

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>(); // 創建堆疊來存儲行星
        
        for (int i = 0; i < asteroids.length; i++) { // 遍歷所有行星
            if (asteroids[i] > 0) { // 如果是向右移動的行星（正值）
                stack.push(asteroids[i]); // 直接推入堆疊
            } else { // 如果是向左移動的行星（負值）
                // 持續彈出較小的向右移動的行星
                while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -asteroids[i]) {
                    stack.pop(); // 彈出較小的行星
                }
                
                // 如果堆疊頂端有相同大小的行星，兩者都摧毀
                if (!stack.isEmpty() && stack.peek() == -asteroids[i]) {
                    stack.pop(); // 彈出堆疊頂端的行星
                } else if (stack.isEmpty() || stack.peek() < 0) { // 如果堆疊為空或頂端是向左移動的行星
                    stack.push(asteroids[i]); // 推入當前行星
                }
                // 如果堆疊頂端有更大的向右移動的行星，當前行星被摧毀，不推入堆疊
            }
        }
        
        // 將堆疊轉換為數組
        int[] res = new int[stack.size()]; // 創建結果數組
        for (int i = res.length - 1; i >= 0; i--) { // 從後往前填充數組
            res[i] = stack.pop(); // 彈出堆疊頂端元素
        }
        
        return res; // 返回結果
    }
}