735. Asteroid Collision
735. Asteroid Collision
Description
tags: Stack difficulty: medium
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
Example 1: Input: asteroids = [5, 10, -5] Output: [5, 10] Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2: Input: asteroids = [8, -8] Output: [] Explanation: The 8 and -8 collide exploding each other.
Example 3: Input: asteroids = [10, 2, -5] Output: [10] Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Example 4: Input: asteroids = [-2, -1, 1, 2] Output: [-2, -1, 1, 2] Explanation: The -2 and -1 are moving left, while the 1 and 2 are moving right. Asteroids moving the same direction never meet, so no asteroids will meet each other.
Note:
- The length of asteroids will be at most 10000.
- Each asteroid will be a non-zero integer in the range [-1000, 1000]..
Solution
一开始的解题思路并不是stack，而是递归，一次将可碰撞的陨石消灭掉，到最后无碰撞就是剩下的陨石，代码如下：
func asteroidCollision(asteroids []int) []int {
if len(asteroids) ==0 {
return asteroids
}
var location int =0
for ;location < len(asteroids) && asteroids[location] < 0;location++{
}
if location == len(asteroids){
return asteroids
}
curLoc := location
for ;location < len(asteroids) && asteroids[location] > 0;location++{
}
if location == len(asteroids){
return asteroids
}
//do one collision
i:=location-1
for ;i>=curLoc;i--{
if abs(asteroids[i]) == abs(asteroids[location]){
return asteroidCollision(append(asteroids[:i], asteroids[location+1:]...))
}
if abs(asteroids[i]) > abs(asteroids[location]) {
return asteroidCollision(append(asteroids[:i+1], asteroids[location+1:]...))
}
}
return asteroidCollision(append(asteroids[:curLoc], asteroids[location:]...))
}
func abs(a int) int{
if a > 0{
return a
}
return -a
}每次都需要从左至右判断，因此时间复杂度为O(n^2)，并不高效。
我们拆解一下子问题，假设左侧的陨石系统是稳定的，每次加入一块新的陨石，调整陨石系统至稳定，加至最后一块陨石后剩下的是稳定的陨石系统，就是我们的答案。
func asteroidCollision(asteroids []int) []int {
if len(asteroids) ==0 {
return asteroids
}
stack := make([]int, 1001)
top := 0
stack[top] = -1001 //barrier
for _,val := range asteroids {
if val > 0 {
top++
stack[top] = val
} else {
for i:=top; i>=0;i--{
if stack[i] < 0 {//push
top++
stack[top] =val
break
} else if stack[i] < abs(val) {
top-- //pop
} else if stack[i] == abs(val){
top-- //pop
break
} else {
break
}
}
}
}
return stack[1:top+1]
}
func abs(a int) int{
if a > 0{
return a
}
return -a
}