【栈】1249 移除无效的括号

题目描述
给你一个由 '('、')' 和小写字母组成的字符串 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)"

作者：97wgl
链接：https://leetcode-cn.com/problems/minimum-remove-to-make-valid-parentheses/solution/yi-chu-wu-xiao-de-gua-hao-zhan-by-97wgl/

解题思路：

1：需要删除最少的 括号，就是删除不匹配的括号。
思路1：

• 最开始想的是可以字符串依次入栈，但是匹配不好操作，
• 后来发现只是需要删除括号，所有可以将括号依次入栈，但是入栈的是括号的下标。
• 但是问题出来了，如果是下标，那么左右括号怎么匹配？
• 可以采用，从字符串中获取当前栈中下标，然后获取具体字符，虽然可以匹配，但是没有匹配的下标需要记录下来。
• 记录下来了，怎么从字符串中删除尼？ 字符串没有提供删除方法

思路1 有个好方法，只是把括号入栈，其余的字符不需要。

思路2：
重点： 默认所有的右边下标是有效的。只把左边括号入栈
维护一个数组，表示要删除的不符合的括号，无效的。也存放下标
使用栈保存左边括号的下标。

• 只把左边括号入栈 （ 。同时入栈的还是下标。
• 使用栈，当第一次放入 （ 的时候，标识这个 （ 下标是 无效的，
• 当遇到是 ） 括号的时候
  如果栈是空的，说明 ） 在 （ 之前出现了，这个也是无效的，要删除的。也要标记。
  如果栈不是空的， 因为这个栈里只放 （ 。所以这个右括号)和上一个出现的左括号(可以组成合法括号，那么当前栈顶的元素的下标是有效的。

存在的问题：
）a（ 这种 结果是a
(a) 这种结果是 （a）

代码：

    private static void minRemoveToMakeValid2(String s) {
        Stack<Integer> bracketIndex = new Stack<>();
        boolean[] invalidIndex = new boolean[s.length()];
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                bracketIndex.push(i);
                invalidIndex[i] = true;
            }
            if (s.charAt(i) == ')') {
                if (bracketIndex.empty()) {
                    invalidIndex[i] = true;
                } else {
                    invalidIndex[bracketIndex.pop()] = false;
                }
            }
        }
        for (int i = 0; i < s.length(); i++) {
            if (!invalidIndex[i]) {
                result.append(s.charAt(i));
            }
        }
        System.out.println(result.toString());
    }