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
wheren
is the length ofnums
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 -> <-
- if you find this rocket is going to right, you put it into stack directly
- 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:
- stack is empty -> push current rocket in
- stack peek is same negative (same direction right to left) -> push current rocket in
- 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)
Top comments (0)