[LeetCode]Asteroid Collision

这道题我们直接需要用到stack，具体的思路是，对于当前数curr:

• 如果curr是正数，压入stack
• 如果curr是负数，当且仅当栈顶有元素，并且是正数，而且小于curr的绝对值，pop栈顶元素
• 如果栈空了或者栈顶元素为负数，curr压入栈
• 如果栈顶元素大于0并且和curr绝对值一样，pop栈顶，继续下一个元素
• 否则，栈顶元素为正，并且大于curr的绝对值，curr被碾碎，继续下一个元素

时间/空间复杂度均为O(N)，代码如下：

	class Solution {
	public:
	vector<int> asteroidCollision(vector<int>& asteroids) {
	stack<int> st;
	for (const auto& asteroid : asteroids)
	{
	if (asteroid > 0)st.push(asteroid);
	else
	{
	while (st.size() && st.top() > 0 && st.top() < abs(asteroid))
	st.pop();
	if (st.size() && st.top() > 0 && st.top() == abs(asteroid))
	st.pop();
	else if (st.empty() || st.top() < 0)
	st.push(asteroid);
	}
	}
	vector<int> res;
	while (st.size()) { res.push_back(st.top()); st.pop(); }
	reverse(res.begin(), res.end());
	return res;
	}
	};

view raw Asteroid Collision.cpp hosted with ❤ by GitHub