735. Asteroid Collision

三刷

91.91 %
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int ast : asteroids) {
            if (ast > 0) {
                stack.push(ast);
            } else {
                while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -ast) {
                    stack.pop();
                }
                if (!stack.isEmpty() && stack.peek() > 0 && stack.peek() == -ast) {
                    stack.pop();
                } else if (stack.isEmpty() || stack.peek() < 0) {
                    stack.push(ast);
                }
                // stack.peek() == -ast || stack.peek() > -ast will destroy ast
            }
        }
        int[] result = new int[stack.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = stack.removeLast();
        }
        return result;
    }
}

一刷

Better Version
12.90 %
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        if (asteroids == null || asteroids.length == 0) {
            return asteroids;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        for (int asteroid : asteroids) {
            if (asteroid > 0 || stack.isEmpty() || stack.getLast() < 0) {
                stack.add(asteroid);
            } else {
                while (!stack.isEmpty() && stack.getLast() > 0 && stack.getLast() < -asteroid) {
                    stack.pollLast();
                }
                if (!stack.isEmpty() && stack.getLast() == -asteroid) {
                    stack.pollLast();
                } else if (stack.isEmpty() || stack.getLast() < 0) {
                    stack.add(asteroid);
                }
            }
        }
        return stack.stream().mapToInt(i -> i).toArray();
    }
}





52.98 %
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        if (asteroids == null || asteroids.length == 0) {
            return asteroids;
        }
        Stack<Integer> stack = new Stack<>();
        for (int asteroid : asteroids) {
            if (asteroid > 0) {
                stack.push(asteroid);
            } else {
                while(!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -asteroid) {
                    stack.pop();
                }
                if (!stack.isEmpty() && stack.peek() == -asteroid) {
                    stack.pop();
                } else if (stack.isEmpty() || stack.peek() < 0 || stack.peek() < -asteroid) {
                    stack.push(asteroid);
                }
            }
        }
        int[] result = new int[stack.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        return result;
    }
}