735-行星碰撞

LeetCode 735. Asteroid Collision

LeetCode-735

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

method: 栈

• 正数就直接入栈
• 负数要考虑几种情况
  • 栈顶元素是正数并且小于nums[i]的相反数，要退栈，这个要while
  • 栈空或者栈顶元素是负数，nums[i]入栈(正数可以放到这种情况里)
  • 否则栈非空并且栈顶是正数，nums[i]是负数，如果栈顶等于-nums[i]，要出栈
• 最后把栈里的元素逆序存到vector里

vector<int> asteroidCollision(vector<int>& nums) {
    stack<int> st;
    for (int i = 0; i < nums.size(); ++i) {
        while (!st.empty() && st.top() > 0 && st.top() < -nums[i]) st.pop();    // 需要出栈的情况，这里不用写nums[i]<0
        if (st.empty() || st.top() < 0 || nums[i] > 0) st.push(nums[i]);    // 可以入栈的情况
        else if (st.top() == -nums[i]) st.pop();    // 还有一种要出栈的情况
    }
    vector<int> ret(st.size());
    for (int i = st.size() - 1; i >= 0; --i) {
        ret[i] = st.top();
        st.pop();
    }
    return ret;
}

为什么不用写nums[i] < 0，因为前边的条件保证栈顶必须是正数，如果nums[i]也是正数，那取反之后肯定会小于栈顶的正数，所以只能是负数才会大于

else已经保证：栈非空，栈顶元素是正数，nums[i]是负数，从这里考虑相等出栈情况