[735. Planetary collision]

source ： Power button （LeetCode）

describe ：

Given an array of integers asteroids, Represents planets on the same line .

For each element in the array , Its absolute value represents the size of the planet , Positive and negative indicate the direction of movement of the planet （ Positive means moving to the right , Negative means moving to the left ）. Every planet moves at the same speed .

Find all the planets left after the collision . Collision rules ： The two planets collide with each other , Smaller planets will explode . If two planets are the same size , Then both planets will explode . Two planets moving in the same direction , There will never be a collision .

Example 1：

 Input ：asteroids = [5,10,-5]
 Output ：[5,10]
 explain ：10  and  -5  After the collision, only  10 . 5  and  10  There will never be a collision .

Example 2：

 Input ：asteroids = [8,-8]
 Output ：[]
 explain ：8  and  -8  After the collision , Both exploded .

Example 3：

 Input ：asteroids = [10,2,-5]
 Output ：[10]
 explain ：2  and  -5  After the collision, there are  -5 .10  and  -5  After the collision, there are  10 .

Tips ：

• 2 <= asteroids.length <= 10⁴
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

Method ： Stack simulation

Use stack st Simulate planetary collision , Traverse the planetary array from left to right asteroids, When we traverse the planet aster when , Using variables alive Record planets aster Does it still exist （ That is, unexploded ）.

When the planet aster Exist and aster < 0, The stack top element is not empty and greater than 0 when , It shows that the two planets move towards each other ： If the top element is greater than or equal to −aster, Then the planet aster Explosion , take alive Set as false; If the stack top element is less than or equal to −aster, Then the planet represented by the top element of the stack explodes , Perform stack out operation . Repeat the above judgment until the conditions are not met , If the last alive It's true , Explain the planet aster It doesn't explode , Will aster Push .

Code ：

class Solution {
    
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
    
        vector<int> st;
        for (auto aster : asteroids) {
    
            bool alive = true;
            while (alive && aster < 0 && !st.empty() && st.back() > 0) {
    
                alive = st.back() < -aster; // aster  Whether there is 
                if (st.back() <= -aster) {
      //  The top planet exploded 
                    st.pop_back();
                }
            }
            if (alive) {
    
                st.push_back(aster);
            }
        }
        return st;
    }
};

Execution time ：4 ms, In all C++ Defeated in submission 99.37% Users of
Memory consumption ：17 MB, In all C++ Defeated in submission 72.79% Users of
Complexity analysis
Time complexity ： O(n), among n Is an array asteroids Size . No more than n Time .
Spatial complexity ： O(1). The return value is not included in the space complexity .
author：LeetCode-Solution