小旭讲解 LeetCode 735. Asteroid Collision
小旭讲解 LeetCode 735. Asteroid Collision

题目

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/
0 0 vote
Article Rating
Subscribe
提醒
guest
1 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments

[…] 小旭讲解 LeetCode 735. 行星碰撞 […]