leetcode-每日一题735. 行星碰撞(栈模拟)

题目链接：https://leetcode.cn/problems/asteroid-collision/

思路

方法一、栈模拟

直接想法

用栈 st 来模拟行星碰撞，遍历 asteroids 数组，对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向，所以只有 st 的栈顶为正，当前 asteroids[i] 元素为负才会发生碰撞，且会一直取出栈顶元素为正的行星比较，直到比他小的正的行星碰完或者为同负的行星才结束

算法

1. 从左往右遍历行星数组 asteroids
2. 使用变量 alive 记录行星 aster 是否还存在（即未发生爆炸）
3. 当 aster < 0 (行星方向向左) && alive == true(行星 aster 是否还存在) && len(st) > 0(栈st不为空) && st[len(st)-1] > 0((行星方向向右))
   1）如果栈顶元素大于等于 −aster，则行星 aster 发生爆炸，将 alive 置为false
   2）如果栈顶元素小于等于 −aster，则栈顶元素表示的行星发生爆炸，执行出栈操作
   3）重复以上判断直到不满足条件，如果最后 alive 为真，说明行星 aster 不会爆炸，则将 aster 入栈

代码示例

func asteroidCollision(asteroids []int) (st []int) {
    
    for _, aster := range asteroids{
    
        alive := true
        for alive && len(st) > 0 && aster < 0 && st[len(st) - 1] > 0{
    
            alive = st[len(st)-1] < -aster // aster 是否存在
            if st[len(st)-1] <= -aster {
       // 栈顶行星爆炸
                st = st[:len(st)-1]
            }
        }
        if alive{
    
            st = append(st, aster)
        }
    }
    return
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组 asteroids 的大小。遍历数组 asteroids 总共需要O(n)的时间。

• 空间复杂度：O(1)。不需要申请额外的空间。