【Leetcode】735. Asteroid Collision

题目地址：

https://leetcode.com/problems/asteroid-collision/

给定一个不含$0$的长$n$数组$A$，表示一个数轴上的小行星的速度，正数代表向右，负数代表向左，绝对值代表小行星的质量。同向的小行星不会相撞，但反向的小行星会相撞，相撞的结果是，质量大的继续存在，小的爆炸；如果质量一样则都爆炸。问最后剩下的小行星的速度状态是什么，返回一个数组。

其实就是模拟相撞的过程。开个栈，遍历$A$，如果遇到了向右的小行星则直接入栈；否则，如果栈空或者栈顶也是向左的小行星，则也入栈，如果栈不空并且栈顶是向右的小行星，则进行相撞操作，直到栈空或者栈顶是向左的小行星为止，同时记录一下当前小行星是否爆炸。如果退出循环的时候当前小行星没有爆炸，则入栈。最后逆序存一下栈，就是答案。代码如下：

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int asteroid : asteroids) {
            if (asteroid > 0) {
                stack.push(asteroid);
            } else {
                if (stack.isEmpty() || stack.peek() < 0) {
                    stack.push(asteroid);
                    continue;
                }
                
                boolean exploded = false;
                while (!stack.isEmpty() && stack.peek() > 0) {
                    if (stack.peek() > -asteroid) {
                        exploded = true;
                        break;
                    } else if (stack.peek() == -asteroid) {
                        exploded = true;
                        stack.pop();
                        break;
                    } else if (stack.peek() < -asteroid) {
                        stack.pop();
                    }
                }
                
                // 如果asteroid没炸，则入栈
                if (!exploded) {
                    stack.push(asteroid);
                }
            }
        }
        
        int[] res = new int[stack.size()];
        int idx = 0;
        while (!stack.isEmpty()) {
            res[idx++] = stack.pop();
        }
        
        // 最后反个序
        reverse(res);
        return res;
    }
    
    private void reverse(int[] A) {
        for (int i = 0, j = A.length - 1; i < j; i++, j--) {
            int tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
        }
    }
}

时空复杂度$O(n)$。