Space Battle

Description

There are a bunch of rockets in space lined up in a row.

You are given a list of integers nums representing each rocket's size and direction. If the number is positive it's going right, and if it's negative it's going left. The value of the number represents the rocket's size.

If two rockets collide, the smaller one will disappear and the larger one will continue on its course unchanged. If they are the same size and they collide, they'll both explode (both numbers are removed). If two rockets are moving in the same direction, they will never collide. The rockets start out equally spaced in the given order and all move at the same speed and become harmless after exploding.

Return the state of the rockets after all collisions.

Constraints:

• n ≤ 100,000 where n is the length of nums

Example 1

Input

nums = [1, 5, 3, -6]

Output

[-6]

Explanation

The last rocket will collide with everything to its left.

---

Example 2

Input

nums = [1, 5, 3, -6, 7]

Output

[-6, 7]

Explanation

-6 and 7 are going in separate directions, and the -6 rocket will destroy everything to its left.

---

Intuition

use a stack to store rocketswe need to do it from left to right, because only one chance the rockets will collide, which is -> <-

1. if you find this rocket is going to right, you put it into stack directly
2. if you find this rocket is going to left, you need check all rockets in stack
   • if stack.peek is to right, and its size smaller than current rocket, just pop it out;
   • after that, here will be 3 situation:
     1. stack is empty -> push current rocket in
     2. stack peek is same negative (same direction right to left) -> push current rocket in
     3. stack peek size is equal current rocket size and direction is opposed -> push peek rocket out

Implementation

import java.util.*;

class Solution {
    public int[] solve(int[] nums) {
        Stack<Integer> stack = new Stack<>();

        for (int rocket : nums) {
            if (rocket > 0) {
                stack.push(rocket);
            } else {
                while (!stack.empty() && stack.peek() > 0 && stack.peek() + rocket < 0) {
                    stack.pop();
                }
                if (stack.isEmpty() || stack.peek() < 0) {
                    stack.push(rocket);
                } else if (stack.peek() + rocket == 0) {
                    stack.pop();
                }
            }
        }

        int[] ans = new int[stack.size()];
        for (int i = ans.length - 1; i >= 0; i--) {
            ans[i] = stack.pop();
        }
        return ans;
    }
}

Time Complexity

• Time: O(n)
• Space: O(n)