小行星碰撞

题目链接

小行星碰撞

题目描述

注意点

• 两个小行星相互碰撞，较小的小行星会爆炸
• 如果两颗小行星大小相同，则两颗小行星都会爆炸
• 每一颗小行星以相同的速度移动
• 正负表示小行星的移动方向（正表示向右移动，负表示向左移动）
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

解答思路

• 首先需要注意的是，本题只有在前一个行星向右移动后一个行星向左移动才会发生碰撞，也就是prev > 0，last < 0
• 另外需要注意的是，当前行星与前一个行星碰撞后如果当前行星没有爆炸（当前行星体积大于前一个行星体积），其有可能继续与更前面的行星碰撞
• 利用栈先进后出的特点，对当前行星与栈顶行星进行判断，关键是要找到什么时候应该将当前行星加入到栈中，什么时候应该将栈顶行星弹出（也就是哪些行星会碰撞，发生碰撞哪些行星会爆炸）
  • 如果当前栈中无元素，则一定不会发生碰撞，直接将当前行星加入到栈中
  • 如果不是栈顶行星向右当前行星向左的情况，则一定不会发生碰撞，直接将当前行星加入到栈中
  • 如果当前行星会发生碰撞，则需要一直循环到无行星能与当前行星碰撞或当前行星已爆炸为止。无行星能与当前行星碰撞，可能是栈中没有行星或栈顶行星也向左移动；当前行星爆炸说明栈顶行星的体积不比当前行星小
• 行星发生碰撞，如果栈顶行星的体积不大于当前行星，则栈顶行星爆炸；如果当前行星的体积不大于栈顶行星，则当前行星爆炸

代码

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> deque = new ArrayDeque<>();
        for (int asteroid : asteroids) {
            if (deque.isEmpty()) {
                deque.offerLast(asteroid);
                continue;
            }
            // 只有之前行星向右当前行星向左才会相撞
            if (!(deque.peekLast() > 0 && asteroid < 0)) {
                deque.offerLast(asteroid);
                continue;
            }
            int curr = -asteroid;
            boolean isAlive = true;
            // 当前向左移动的行星仍然存活、之前有向右移动的行星才会相撞
            while (isAlive && !deque.isEmpty() && deque.peekLast() > 0) {
                // 之前行星只有比当前行星小，当前行星才存活
                isAlive = deque.peekLast() < curr;
                // 之前行星只有比当前行星大，之前行星才存活
                if (deque.peekLast() <= curr) {
                    deque.pollLast();
                }
            }
            if (isAlive) {
                deque.offerLast(asteroid);
            }
        }
        int[] res = new int[deque.size()];
        int i = 0;
        while (!deque.isEmpty()) {
            res[i] = deque.pollFirst();
            i++;
        }
        return res;
    }
}

关键点

• 行星什么情况下会碰撞
• 行星什么情况下会爆炸
• 两颗行星方向不同并不一定就会碰撞，而是只有前一个行星向左移动后一个行星向右移动才会碰撞