【题解】牛牛的01游戏

题意

给你一个01构成的字符串，字符串中0和0相邻时会变成1，1和1相邻时会消失，0和1相邻时没用变化，且合并和消失操作优先与左边元素进行，求最后的字符串会变成什么。

思路

实际上这题和用栈进行括号匹配是一样的，我们创建一个栈来模拟这个过程，首先若栈为空则入栈，若栈顶元素与需要入栈的元素不会发生合并或者消除操作则将元素入栈，接着考虑若栈顶为1，新入栈元素也为1则弹栈完成消除操作，若栈顶元素为0，新入栈元素为0，则先弹栈，然后判断站内下一个元素是否为1，若为1则再次弹栈，否则将1入栈。

复杂度

时间复杂度为
空间复杂度为

代码

class Solution {
public:
    /**
     * 
     * @param str string字符串 
     * @return string字符串
     */
    string Solve(string str) {
        // write code here
       stack<char>s;
        for(int i=0;i<str.length();i++)
        {
           if(s.empty())
               s.push(str[i]);
           else if((s.top()=='0'&&str[i]=='1')||(s.top()=='1'&&str[i]=='0'))
               s.push(str[i]);
           else
           {
               char tmp=s.top();
               if(tmp=='1'&&str[i]=='1')s.pop();
               else if(tmp=='0'&&str[i]=='0')
               {
                   s.pop();
                   if(!s.empty()&&s.top()=='1')s.pop();
                   else s.push('1');
               }
           }
        }
        int cnt=0;
        string ans="";
        while(!s.empty())
        {
            ans+=s.top();
            s.pop();
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};