LeetCode 75 part 06 栈

2390.从字符串中移除星号

思路：把元素加入栈中，遇到 * 号直接弹出栈顶元素

class Solution {
public:string removeStars(string s) {stack<char>st;for(int i=0;i<s.size();i++){//字符加入栈，遇到星号弹出栈if(s[i]!='*') st.push(s[i]);else st.pop();}int n=st.size();for(int i=n-1;i>=0;i--){//把栈中元素倒序赋值给schar mid=st.top();s[i]=mid;st.pop();}return s.substr(0,n);//截取s的结果部分}
};

735.小行星碰撞

分析：只有左边向右，右边向左时，两个星球才会相撞

思路一：使用 vector 模拟栈

        遍历数组，当出现两个星球相撞时

• 1.两个星球相等：栈顶弹出
• 2.栈顶的元素大：跳过
• 3.栈顶的元素小：栈顶弹出，当前遍历星球存活，还需要判断下一个栈顶情况

        所以，栈顶元素小的情况下，可能当前遍历星球会存活，所以引入 bool 变量记录

class Solution {
public:vector<int> asteroidCollision(vector<int>& asteroids) {vector<int>res;int n=asteroids.size();for(int it:asteroids){//遍历数组bool alive=true;//判断当前行星是否存活while(alive && it<0 && !res.empty() && res.back()>0){alive=res.back()<-it;//记录当前值大于栈顶值，当前值存活if(res.back()<=-it) res.pop_back();//弹出较小的栈顶}if(alive) res.push_back(it);//当前行星存活，直接加入}return res;}
};