思路

  1. 使用栈解决;
  2. 复用栈空间,提高空间利用率

代码

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]

}

结果

file

最后修改日期: 2022年7月14日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。