标签
栈
数组
日期
Oct 11, 2022
剑指 Offer II 037. 小行星碰撞
题目描述
给定一个整数数组
asteroids，表示在同一行的小行星。对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
示例 1：
示例 2：
示例 3：
示例 4：
题目解析
思路：
- 在栈是空或者当前加入行星方向向右的时候也就是大于等于0的时候是不会发生碰撞的，所以直接加入栈即可
- 然后接下来就要分情况来考虑，这个情况的前提是行星数组中的下一个元素小于0
- 栈顶元素小于0的时候，二者运动方向一致，不会发生碰撞，所以直接压入栈中
- 如果下一个元素和栈顶元素之和小于0即栈顶元素比较小，执行退栈
- 如果下一个元素和栈顶元素之和大于0即栈顶元素比较大，i++比较下一个行星