Force deduction solution summary 735 planetary collision

Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

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 <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/asteroid-collision
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  To solve this problem, you can use stack . Traverse left to right , If it is a positive number, it will be put on the stack . If the number is negative, the absolute value is compared with the number at the top of the stack ,
*  If it is greater than, the stack will pop out of the stack , Continue to compare the next in the stack ;
*  If less than, continue to cycle ;
*  If equal to, the stack comes out of the stack , And continue the cycle .
*  There is a situation , If the stack is empty , And the reading is still negative , This situation can be directly added to the final result set .

Code ：

public class Solution735 {

    public int[] asteroidCollision(int[] asteroids) {
        List<Integer> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < asteroids.length; i++) {
            int value = asteroids[i];
            if (value > 0) {
                stack.add(value);
                continue;
            }
            int abs = Math.abs(value);
            while (stack.size() > 0) {
                Integer top = stack.peek();
                if (abs > top) {
                    stack.pop();
                } else if (abs < top) {
                    break;
                } else {
                    //value Change it to 0, Does not represent a collection 
                    value = 0;
                    stack.pop();
                    break;
                }
            }
            if (stack.size() == 0 && value != 0) {
                list.add(value);
            }
        }
        list.addAll(stack);
        int[] ints = list.stream().mapToInt(Integer::intValue).toArray();
        return ints;
    }
}