题目
思路 – 栈
该题数据的处理过程符合 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/
[…] 小旭讲解 LeetCode 735. 行星碰撞 […]