LeetCode 1249. 移除无效的括号（栈+set / deque）

示例 1：
输入：s = "lee(t(c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。

示例 2：
输入：s = "a)b(c)d"
输出："ab(c)d"

示例 3：
输入：s = "))(("
输出：""
解释：空字符串也是有效的

示例 4：
输入：s = "(a(b(c)d)"
输出："a(b(c)d)"
 
提示：
1 <= s.length <= 10^5
s[i] 可能是 '('、')' 或英文小写字母

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string ans;
        stack<int> stk;
        set<int> del;//要删除的idx存储取来
        for(int i = 0; i < s.size(); ++i)
        {
        	if(s[i] == '(')
        		stk.push(i);
        	else if(s[i] == ')')
        	{
        		if(!stk.empty())
        			stk.pop();
        		else
        			del.insert(i);//栈为空，碰到 ),要删除
        	}
        }
        while(!stk.empty())//结束后栈不为空，也要删除
        {
        	del.insert(stk.top());
        	stk.pop();
        }
        auto it = del.begin();//遍历要删除的
        for(int i = 0; i < s.size(); ++i)
        {
        	if(it != del.end() && i == *it)
        	{
                it++;
                continue;//跳过要删除的
            }
        	ans += s[i];
        }
        return ans;
    }
};

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string ans;
        stack<int> stk;
        unordered_set<int> del;
        for(int i = 0; i < s.size(); ++i)
        {
        	if(s[i] == '(')
        		stk.push(i);
        	else if(s[i] == ')')
        	{
        		if(!stk.empty())
        			stk.pop();
        		else
        			del.insert(i);
        	}
        }
        while(!stk.empty())
        {
        	del.insert(stk.top());
        	stk.pop();
        }
        for(int i = 0; i < s.size(); ++i)
        {
        	if(del.count(i))
                continue;
        	ans += s[i];
        }
        return ans;
    }
};

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string ans;
        deque<int> q;
        for(int i = 0; i < s.size(); ++i)
        {
        	if(s[i] == '(')
        		q.push_back(i);
        	else if(s[i] == ')')
        	{
        		if(!q.empty() && s[q.back()]=='(')
        			q.pop_back();
        		else
        			q.push_back(i);;
        	}
        }
        for(int i = 0, j = 0; i < s.size(); ++i)
        {
        	if(j < q.size() && i == q[j])
            {
                j++;
                continue;
            }
        	ans += s[i];
        }
        return ans;
    }
};