735. Asteroid Collision

time: O(n)

space:O(n)

case 1: positive income, push

case 2: negtive income, stack has value && stack peek is positive

Input: asteroids = [5,10,-5]
Output: [5,10]

5 10 -5. ⇒ stack [5, 10] 如果-5, stack 維持

但如果是 -15 ⇒ 10, 5 都會被幹掉, 所以用一個 while 去判斷

case 3: stack 一開始就空的話 或 stack 第一個是 負的, 放入

Input: asteroids = [-2,-1,1,2]
Output: [-2,-1,1,2]

case 4: peek 和當前, 正負一樣, 抵銷

Input: asteroids = [8,-8]
Output: []

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        
        for (int asteroid: asteroids) {
            if (asteroid > 0) { // case 1
                stack.push(asteroid);
                
            } else { // asteroid 負的 case
                // case 2
                // top 是正時, 才要跟負的拿來抵銷
                while (!stack.isEmpty() && stack.peek() > 0 && (stack.peek() < Math.abs(asteroid))) { // 5 10 -15
                    stack.pop();
                }
                
                // case 3
                // 一直是負的狀況, 一直 push
                if (stack.isEmpty() || stack.peek() < 0) {
                    stack.push(asteroid);
                } else if (asteroid + stack.peek() == 0) { // case 4
                    stack.pop(); // 抵銷
                }
            }
        }
        
        // reverse 放入結果
        int res[] = new int[stack.size()];
        for (int i = stack.size() - 1; i >=0 ; i--) {
            res[i] = stack.pop();
        }
        return res;
    }
}