Cars sit on a straight rail. cars[i] is a non-zero integer: its absolute value is the car's weight and its sign is its direction (positive moves right, negative moves left). All cars move at the same speed.
When two cars meet, the lighter one is knocked off the rail; if they weigh the same both are knocked off. Two cars moving in the same direction never meet. Return the list of cars that remain, in their original order.
Examples
Input: cars = [5, 10, -5]
Output: [5, 10]
Explanation: 10 and -5 collide; -5 is knocked off. 5 and 10 never meet.
Input: cars = [8, -8]
Output: []
Input: cars = [10, 2, -5]
Output: [10]
Explanation: -5 knocks off 2, then is knocked off by 10.
Constraints
0 <= len(cars) <= 10**5-1000 <= cars[i] <= 1000,cars[i] != 0- Target:
O(n)time
Goals
- Only a right-moving car on the stack can collide with a new left-moving car
- Resolve a chain of collisions with a while loop against the stack top