📃 题目描述

题目链接：

• 剑指 Offer II 037. 小行星碰撞 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 735. 行星碰撞 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

🔔 解题思路

题目需要明确两点：

1）只有一种情况下会发生碰撞：栈顶行星往右走（> 0）, 当前行星往左走（< 0）

2）发生爆炸后，若当前行星仍然存活，那么他会继续向左推进

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        while (index < asteroids.length) {
            // 只有栈顶行星向右，当前行星向左，才会发生碰撞
            if (!stack.isEmpty() && asteroids[index] < 0 && stack.peek() > 0) {
                // 1. 栈顶行星大小 < 当前行星：栈顶行星爆炸，当前行星继续推进
                if (stack.peek() < -asteroids[index]) {
                    stack.pop();
                }
                // 2. 栈顶行星大小 == 当前行星：共同爆炸，进入下一个行星的处理
                else if (stack.peek() == -asteroids[index]) {
                    stack.pop();
                    index ++;
                }
                // 3. 栈顶行星大小 > 当前行星：当前行星爆炸，进入下一个行星的处理
                else {
                    index ++;
                }
            }
            // 4. 不发生碰撞或者栈为空
            else {
                stack.push(asteroids[index]);
                index ++;
            }
        }
        

        return stack.stream().mapToInt(Integer::intValue).toArray();
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：