移除无效的括号 图解题解

这道题到底在问什么

输入

s = "lee(t(c)o)de)"

输出

"lee(t(c)o)de"（删掉末尾多出来的右括号）

输入

s = "a)b(c)d"

输出

"ab(c)d"（删掉开头无配对的右括号）

输入

s = "))(("

输出

""（四个括号全无效，删光）

最优解：一步一步想明白

1. 3核心一句话：栈存「等待配对的左括号下标」。右括号空栈即删，扫完栈中残留即删。记住这套，下面每帧都在套它。
2. 4开局：指针还没进入字符串，栈是空的。橙色将标记「正在看」的字符，左边竖栏是栈（底→顶）。
3. 5先扫一眼 s="a(b)c)d("：里面有 2 个左括号、2 个右括号。它们能否两两配上，得用栈一位位走才知道。从第 0 位开始。
4. 6看第 0 位「a」。先判断它是不是括号，结论是字母，那它和括号配对无关。
5. 7字母「a」直接保留、完全不碰栈。栈里仍是 0 个等待配对的左括号，继续往后走。
6. 8看第 1 位「(」。左括号先不下结论，把它的下标 1 压进栈，排队等一个右括号来配对。
7. 9下标 1 入栈，现在栈顶是它。只要后面来个右括号，这一对就能配上。
8. 10看第 2 位「b」。先判断它是不是括号，结论是字母，那它和括号配对无关。
9. 11字母「b」直接保留、完全不碰栈。栈里仍是 1 个等待配对的左括号，继续往后走。
10. 12看第 3 位「)」。栈不空，栈顶是下标 1 的左括号，正好和它配成一对。
11. 13配对成功！弹出栈顶下标 1。位置 1 的「(」和位置 3 的「)」都是合法的，保留。
12. 14看第 4 位「c」。先判断它是不是括号，结论是字母，那它和括号配对无关。
13. 15字母「c」直接保留、完全不碰栈。栈里仍是 0 个等待配对的左括号，继续往后走。
14. 16看第 5 位「)」。栈是空的，左边没有任何待配的左括号，这个右括号是多余的，标记删除。
15. 17下标 5 进入「待删」名单。这是第一类坏括号：右括号孤立无援。继续往后扫。
16. 18看第 6 位「d」。先判断它是不是括号，结论是字母，那它和括号配对无关。
17. 19字母「d」直接保留、完全不碰栈。栈里仍是 0 个等待配对的左括号，继续往后走。
18. 20看第 7 位「(」。左括号先不下结论，把它的下标 7 压进栈，排队等一个右括号来配对。
19. 21下标 7 入栈，现在栈顶是它。只要后面来个右括号，这一对就能配上。
20. 22整串扫完。栈里若还有元素，它们都是「等不到右括号」的左括号，属于第二类坏括号，下面逐个清掉。
21. 23栈顶下标 7 的「(」始终没等来右括号，标记删除。栈剩 0 个，继续清。
22. 24栈清空了，待删名单确定为下标 { 5、7 }。把没被标记的字符按原顺序拼起来，就是答案。
23. 25跳过下标 5、7，剩下的字符拼成 "a(b)cd"，所有括号都配对合法，且只删了最少的 2 个。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        remove = set()
        stack = []
        for i, ch in enumerate(s):
            if ch == '(':
                stack.append(i)
            elif ch == ')':
                if stack:
                    stack.pop()
                else:
                    remove.add(i)
        remove.update(stack)
        return ''.join(ch for i, ch in enumerate(s) if i not in remove)

#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
    string minRemoveToMakeValid(string s) {
        vector<int> st;
        vector<int> remove(s.size());
        for (int i = 0; i < (int)s.size(); ++i) {
            if (s[i] == '(') st.push_back(i);
            else if (s[i] == ')') {
                if (!st.empty()) st.pop_back();
                else remove[i] = 1;
            }
        }
        for (int i : st) remove[i] = 1;
        string ans;
        for (int i = 0; i < (int)s.size(); ++i) if (!remove[i]) ans.push_back(s[i]);
        return ans;
    }
};

import java.util.*;
class Solution {
    public String minRemoveToMakeValid(String s) {
        boolean[] remove = new boolean[s.length()];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') st.push(i);
            else if (c == ')') {
                if (st.isEmpty()) remove[i] = true;
                else st.pop();
            }
        }
        while (!st.isEmpty()) remove[st.pop()] = true;
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < s.length(); i++) if (!remove[i]) ans.append(s.charAt(i));
        return ans.toString();
    }
}

复杂度

面试官可能追问