题目大意：
移除无效的括号
给你一个由 '('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
- 空字符串或只包含小写字母的字符串
- 可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
- 可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」
示例 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^5s[i]可能是'('、')'或英文小写字母
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1249
解题思路分析：
题目要求删除无效的括号，所谓有效的括号一定是正括号加上反括号按顺序成对出现，关于有效括号的题目之前做过很多，关键思路是循环字符串，使用Stack来保存已经出现的正括号，当遇见反括号时，查看Stack中是否含有正括号，如果有，就从Stack中pop出一个，保证与当前反括号配对。如果没有，说明当前反括号是多余的，需要被删除。循环结束后，如果Stack中还有剩余的正括号，说明这些也是多余的，应该被删除。未被删除的部分即是答案。
写代码时，我们定义一个boolean数组，记录哪些位置是需要删除的，再定义一个Stack，用来保存出现过的正括号的下标。
实现代码：
public String minRemoveToMakeValid(String s) {
// 应被删除的位
boolean[] wrong = new boolean[s.length()];
// 记录正括号出现的下标
Stack<Integer> stack = new Stack<>();
for(int i=0;i<s.length();i++){ // 循环字符串
char c = s.charAt(i); // 当前字符
if('('==c){ // 如果是正括号
stack.push(i); // 加入到Stack中
}else if(')'==c){ // 如果是反括号
if(stack.size()>0){ // 如果Stack中有正括号
// pop出该正括号
// 说明当前反括号与pop出的正括号是有效的
stack.pop();
}else{ // 如果Stack中没有正括号
// 当前反括号是多余的，应被删除
wrong[i]=true;
}
}
}
while(stack.size()>0){ // stack中剩余的正括号是多余的
wrong[stack.pop()]=true;
}
StringBuilder sb = new StringBuilder(); // 返回结果
for(int i=0;i<s.length();i++){
if(!wrong[i]){ // 所有不需要被删除的字符可以组成返回结果
sb.append(s.charAt(i));
}
}
return sb.toString();
} 本题解法执行时间为29ms。
Runtime: 29 ms, faster than 49.12% of Java online submissions for Minimum Remove to Make Valid Parentheses.
Memory Usage: 38.4 MB, less than 100.00% of Java online submissions for Minimum Remove to Make Valid Parentheses.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1249-minimum-remove-to-make-valid-parentheses-解题思路分析/