题目链接: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)。不需要申请额外的空间。