Asteroid Collision

735. 小行星碰撞

分析

栈的意义：用一个栈 res 保存当前未爆炸的小行星。栈中元素表示这些小行星在当前状态下可以安全存在
碰撞处理逻辑：
- 遍历数组中的每颗小行星：
- 如果小行星向右移动（正数），直接将其加入栈中
- 如果小行星向左移动（负数），检查栈顶元素：
- 如果栈顶是向右移动的小行星且比当前小行星小（绝对值），栈顶小行星爆炸，当前小行星继续向左检测
- 如果栈顶是向右移动的小行星且与当前小行星大小相等，两者都爆炸
- 如果栈为空或栈顶为负数（同向移动），当前小行星直接入栈
最终状态：
- 遍历完成后，栈中的小行星即为剩下的未爆炸小行星

时间复杂度

每颗小行星最多入栈和出栈一次

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution
{
public:
    vector<int> asteroidCollision(vector<int>& asteroids)
    {
        std::vector<int> res; // 用作栈
        for (int x : asteroids)
        {
            if (x > 0)
                res.push_back(x); // 向右移动的小行星直接入栈
            else
            {
                // 检测栈顶的小行星是否与当前小行星碰撞
                while (res.size() && res.back() > 0 && res.back() < -x)
                    res.pop_back(); // 栈顶小行星爆炸
                // 检查是否当前小行星与栈顶大小相等
                if (res.size() && res.back() == -x)
                    res.pop_back(); // 两颗小行星同时爆炸
                // 栈为空或栈顶为负数，当前小行星入栈
                else if (res.empty() || res.back() < 0)
                    res.push_back(x);
            }
        }
        return res;
    }
};