思路
- 使用栈解决;
- 复用栈空间,提高空间利用率
代码
func asteroidCollision(asteroids []int) []int {
stack := make([]int, 0, 0)
// 复用栈空间
p := 0
for _, ast := range asteroids{
// 空栈或正数或连续负数,直接栈长度+1
if p == 0 || ast > 0 || (ast<0 && stack[p-1]<0){
if p==len(stack){
stack = append(stack, ast)
}else{
stack[p] = ast
}
p += 1
continue
}
// 负数,往下判断,直至循环退出
if ast<0{
for ;;{
// 打到栈空,栈长度为1
if p==0{
stack[0] = ast
p = 1
break
}
// 遇到负数,栈长度+1
if stack[p-1] < 0{
if p==len(stack){
stack = append(stack, ast)
}else{
stack[p] = ast
}
p += 1
break
}
// 正数,但相等,终止,且栈长度-1
if stack[p-1] > 0 && -ast == stack[p-1]{
p-=1
break
}
// 正数,但小于它,中止
if stack[p-1] > 0 && -ast < stack[p-1]{
break
}
// 正数,但大于它,继续
if stack[p-1] > 0 && -ast > stack[p-1]{
p-=1
}
}
}
}
return stack[:p]
}
结果
Post Views: 476
留言