題目

給定一個整數陣列 asteroids，表示在同一行的行星。

對於陣列中的每一個元素，其絕對值表示行星的大小，正負表示行星的移動方向（正表示向右移動，負表示向左移動）。

每一顆行星以相同的速度移動。

找出碰撞後剩下的所有行星。碰撞規則：兩個行星相互碰撞，較小的行星會爆炸。

如果兩顆行星大小相同，則兩顆行星都會爆炸。兩顆移動方向相同的行星，永遠不會發生碰撞。

示例 1:輸入: asteroids = [5, 10, -5] 輸出: [5, 10]

解釋: 10 和 -5 碰撞後只剩下 10。 5 和 10 永遠不會發生碰撞。

示例 2:輸入: asteroids = [8, -8] 輸出: []

解釋: 8 和 -8 碰撞後，兩者都發生爆炸。

示例 3:輸入: asteroids = [10, 2, -5] 輸出: [10]

解釋: 2 和 -5 發生碰撞後剩下 -5。10 和 -5 發生碰撞後剩下 10。

示例 4:輸入: asteroids = [-2, -1, 1, 2] 輸出: [-2, -1, 1, 2]

解釋: -2 和 -1 向左移動，而 1 和 2 向右移動。

由於移動方向相同的行星不會發生碰撞，所以最終沒有行星發生碰撞。

說明:陣列 asteroids 的長度不超過 10000。

每一顆行星的大小都是非零整數，範圍是 [-1000, 1000] 。

解題思路分析

1、棧輔助；時間複雜度O(n)，空間複雜度O(n)

func asteroidCollision(asteroids []int) []int {	left := make([]int, 0)	right := make([]int, 0)	for i := 0; i < len(asteroids); i++ {		if asteroids[i] > 0 {			right = append(right, asteroids[i])		} else {			if len(right) > 0 {				for {					if len(right) == 0 {						left = append(left, asteroids[i])						break					}					sum := asteroids[i] + right[len(right)-1]					if sum == 0 {						right = right[:len(right)-1]						break					} else if sum > 0 {						break					} else {						right = right[:len(right)-1]					}				}			} else {				left = append(left, asteroids[i])			}		}	}	return append(left, right...)}

總結

Medium題目，使用棧進行模擬操作即可