小行星碰撞
# 📃 题目描述
题目链接:
- 剑指 Offer II 037. 小行星碰撞 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 735. 行星碰撞 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
# 🔔 解题思路
题目需要明确两点:
1)只有一种情况下会发生碰撞:栈顶行星往右走(> 0), 当前行星往左走(< 0)
2)发生爆炸后,若当前行星仍然存活,那么他会继续向左推进
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
int index = 0;
while (index < asteroids.length) {
// 只有栈顶行星向右,当前行星向左,才会发生碰撞
if (!stack.isEmpty() && asteroids[index] < 0 && stack.peek() > 0) {
// 1. 栈顶行星大小 < 当前行星:栈顶行星爆炸,当前行星继续推进
if (stack.peek() < -asteroids[index]) {
stack.pop();
}
// 2. 栈顶行星大小 == 当前行星:共同爆炸,进入下一个行星的处理
else if (stack.peek() == -asteroids[index]) {
stack.pop();
index ++;
}
// 3. 栈顶行星大小 > 当前行星:当前行星爆炸,进入下一个行星的处理
else {
index ++;
}
}
// 4. 不发生碰撞或者栈为空
else {
stack.push(asteroids[index]);
index ++;
}
}
return stack.stream().mapToInt(Integer::intValue).toArray();
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10