小旭讲解 LeetCode 735. 行星碰撞

题目

思路 – 栈

该题数据的处理过程符合 FILO（先进后出）的规则，所以天然可以用栈来处理。

枚举数组中的每一个元素 $A[i]$ ，根据 $A[i]$ 与栈顶元素（ $st.top()$ ）的关系进行相应处理即可。

代码

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& A) {
        stack<int> st;
        if (A.empty()) return {};
        if (A.size()==1) return A;
        vector<int>ans;
        for (int i=0;i<A.size();++i) {
            bool push=true;
            while(!st.empty() && st.top() > 0 && A[i] < 0) {
                if (st.top() == -A[i]) {
                    st.pop();
                    push=false;
                    break;
                } else if (st.top() < -A[i]) {
                    st.pop();
                    push=true;
                } else {
                    push=false;
                    break;
                }
            }
            if (push) st.push(A[i]);
        }
        while (!st.empty()) {
            ans.push_back(st.top());
            st.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

欢迎分享，引用。若转载，请联系我，谢谢配合。
本文地址：https://qoogle.top/xiaoxu-tutorial-leetcode-735-asteroid-collision/