Sword finger offer II 037 Asteroid collision

Summary

Use the stack to process whether two adjacent planets collide .

subject

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

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

Find all the asteroids 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 .

link ：https://leetcode.cn/problems/XagZNi

Ideas

I little interesting .

It's actually , Compare two adjacent values , Look at the sign first .

• If the symbols are the same , All remain .
• If the symbols are reversed
  • The former is negative , The latter is positive , Then the two do not conflict , All reserved .
  • The former is positive , The latter is negative , Then the number with the largest absolute value will be reserved .

The first idea is , Can be matched in an array to handle , But for removing elements from an array , Or reuse the elements that appeared before , It's still a bit of a hassle .

The key is , The asteroid you met in the back , Will continue to hit you .

The stack is still used here .

solution ： Stack

Code

public int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();
    int i = 0;
    while (i < asteroids.length) {
        int current = asteroids[i];
        //  When the stack is empty , Direct stack 
        if (stack.size() == 0) {
            stack.push(current);
            i++;
            continue;
        }

        int peek = stack.peek();
        if (peek > 0 && current < 0) {
            //  A collision occurs 
            int result = peek + current;
            //  Compare their absolute values 
            if (result < 0) {
                //  Stack top absolute value is small , Then it was collided and exploded , Out of the stack 
                stack.pop();
            } else if (result == 0) {
                //  perish together 
                stack.pop();
                i++;
            } else {
                i++;
            }
        } else {
            stack.push(current);
            i++;
        }
    }
    int[] result = new int[stack.size()];
    for (int j = result.length - 1; j >= 0; j--) {
        result[j] = stack.pop();
    }
    return result;
}

Submit results

The above judgment is too verbose , Simplify the code , as follows ：

public int[] asteroidCollision(int[] asteroids) {
    Stack<Integer> stack = new Stack<>();
    int i = 0;
    while (i < asteroids.length) {
        int current = asteroids[i];
        //  When the stack is empty , Direct stack 
        if (stack.isEmpty() || stack.peek() < 0 || current > 0) {
            stack.push(current);
            i++;
            continue;
        }
        int peek = stack.peek();
        //  Only the top of the stack is positive , The current element is negative , The collision will happen 
        if (peek <= -current) {
            //  Stack top absolute value is small , Then it was collided and exploded , Out of the stack 
            stack.pop();
            if (peek < -current) {
                continue;
            }
        }
        i++;
    }
    int[] result = new int[stack.size()];
    for (int j = result.length - 1; j >= 0; j--) {
        result[j] = stack.pop();
    }
    return result;
}

Ah, this , Time and memory have increased ……