LeetCode735. 行星碰撞

题目描述

本题目来自LeetCode上的『735. 行星碰撞』

给定一个整数数组 asteroids，表示在同一行的行星。

对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。

找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例1：

输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

提示

2 <= asteroids.length <= 10^4
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

题解1 - 栈

需要注意的一点是： 当左边的行星向右，右边的行星向左时，两个行星才会相撞，即 $[1,-1]$ 的形式会相撞，而 $[-1,1]$ 的形式不会相撞。

从左到右遍历数组，使用栈保存存在的行星，设当前遍历到的元素为 $i$，栈顶元素为 $u$，有以下几种情况：

栈为空，将 $i$ 入栈。
$u<0$，无论 $i$ 向左还是向右，都不会相撞，将 $i$ 入栈。
$u>0 \wedge i>0$，不会相撞，将 $i$ 入栈。
$u>0 \wedge i<0$，会相撞，又有以下情况：
- $u\le -i$，$u$ 会消失，需要将 $u$ 出栈，继续比较下一个栈顶和 $i$。
- $u\ge -i$，$i$ 会消失，$i$ 不入栈。

由于使用栈实现，在返回答案的时候还需要将栈中元素逆序。

代码

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        int n = asteroids.size();
        stack<int> st;
        
        for (const auto& a: asteroids) {
            bool flag = true;
            while (flag && a < 0 && !st.empty() && st.top() > 0) {
                if (st.top() >= -a) flag = false;
                if (st.top() <= -a) st.pop();
            }
            if (flag) st.emplace(a);
        }

        vector<int> ans;
        while (!st.empty()) {
            ans.emplace_back(st.top());
            st.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

复杂度分析

时间复杂度：$O(n)$
空间复杂度：$O(n)$

题解2 - 模拟栈

我们可以使用向量模拟题解1中栈的实现。从而省去逆序的步骤。

代码

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        int n = asteroids.size();
        vector<int> st;
        for (const auto& a: asteroids) {
            bool flag = true;
            while (flag && a < 0 && !st.empty() && st.back() > 0) {
                if (st.back() >= -a) flag = false;
                if (st.back() <= -a) st.pop_back();
            }
            if (flag) st.emplace_back(a);
        }
        return st;
    }
};

或者

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> ans;
        copy_if(asteroids.begin(), asteroids.end(), back_inserter(ans), 
        [&](const int& i) {
            int u;
            while (i < 0 && ans.size() && (u = ans.back()) > 0) {
                if (u <= -i) ans.pop_back();
                if (u >= -i) return false;
            }
            return true;
        });
        
        return ans;
    }
};