題目

• 概述：給定一個數(shù)組，代表移動速度相同的行星，數(shù)組元素的絕對值表示行星的大小，正負代表行星的移動方向（左負右正），移動方向不同的行星會發(fā)生碰撞，小的行星遇到大的行星會爆炸，大小相同的行星相遇都會爆炸，問最后剩下哪些行星

• 輸入：行星數(shù)組，長度范圍[0, 10000]

• 輸入子項：非零整數(shù)，大小范圍[-1000, 1000]

• 輸出：碰撞后最終剩下的行星數(shù)組

• 出處：https://leetcode-cn.com/problems/asteroid-collision/

思路

• 由于需要記錄之前的行星信息用來判斷是否會發(fā)生碰撞，所以考慮用棧實現(xiàn)

• 遍歷行星數(shù)組：

  1. 正數(shù) => 直接入棧
  2. 負數(shù)：
     1. 棧為空 => 直接入棧
     2. 棧頂元素為負數(shù) => 直接入棧
     3. 棧頂元素為正數(shù)：
        1. 當前元素絕對值 == 棧頂元素絕對值 => 棧頂元素出棧
        2. 當前元素絕對值 > 棧頂元素絕對值 => 棧頂元素出棧，重復

• 棧中所剩元素即為碰撞后最終剩下的行星

代碼

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < asteroids.length; ++i) {
            if (asteroids[i] > 0) {
                stack.push(asteroids[i]);
            } else {
                while (true) {
                    if (stack.isEmpty() || stack.peek() < 0) {
                        stack.push(asteroids[i]);
                        break;
                    } else {
                        if (asteroids[i] + stack.peek() == 0) {
                            stack.pop();
                            break;
                        } else if (asteroids[i] + stack.peek() < 0) {
                            stack.pop();
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        
        int[] result = new int[stack.size()];
        for (int i = stack.size() - 1; i >= 0; --i) {
            result[i] = stack.pop();
        }
        return result;
    }
}