LeetCode75-735-Asteroid-Collision

🧠 思路总结

只有在一种情况下才会发生碰撞：左边的往右（+），右边的往左（-）。后面新的元素要和前面（最后）的元素进行反复比较，所以使用Stack。

❗ 易错点 / 小坑

• 注意最后要翻转stack

✅ 代码（Java）

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int x : asteroids) {
            boolean alive = true;
            while (alive && x < 0 && !stack.isEmpty() && stack.peek() > 0) {
                int top = stack.peek();
                if (Math.abs(top) < Math.abs(x)) {
                    stack.pop();
                } else if (Math.abs(top) == Math.abs(x)) {
                    stack.pop();
                    alive = false;
                } else {
                    alive = false;
                }
            }
            if (alive) {
                stack.push(x);
            }
        }
        int[] res = new int[stack.size()];
        for (int i = res.length - 1; i >= 0; i--) {
            res[i] = stack.pop();
        }
        return res;
    }
}