删除无效的括号 图解题解

删除无效的括号在问什么

字符串里混着左右括号和小写字母，要求删掉最少数量的括号，让剩下的串合法——每个左括号都能配到它右边的一个右括号。字母不参与配对、原样保留。这题按删除数量最少来衡量方案好坏，所以核心是想清楚：到底哪些括号是「非删不可」的，除此之外一个都不多删。

为什么想到用平衡计数器 bal

先问一个串怎样才算合法。从左往右数，用 bal 表示「目前左括号比右括号多出几个」：遇左括号加一，遇右括号减一。合法等价于两件事同时成立——扫描全程 bal 从不变负（每个右括号出现时左边都有闲置的左括号等它），且扫完 bal 归零（左括号也都配上了）。

这个刻画直接暴露了谁是多余的：某个右括号让 bal 要变负，说明它左边的左括号已经全被前面的右括号配光了，无论后面发生什么，它都永远配不上对——这就是一个必删的括号。反过来，扫完后 bal 还大于 0，说明有左括号到最后也没等来配对，它们同样必删，只是位置在串的尾部一侧。

为什么必须正反各扫一遍

从左到右的一遍扫描只能当场揪出多余的右括号，因为右括号非法与否取决于它左边的情况，扫到它时证据已经齐了。可多余的左括号不行：左括号能不能配上，取决于它右边还有没有右括号，正向扫到它时未来还没发生，没法判它死刑。

解决办法是对称地反着来一遍：从右往左扫，把右括号当开方、左括号当闭方，bal 的含义变成「右括号比左括号多几个」，让 bal 变负的左括号就是配不上的，删掉。两遍合起来，多余的右括号和左括号都被清干净，剩下的串前缀性质与总量守恒同时满足，必然合法。

凭什么说这样删得最少

每一次删除都发生在「铁证已到手」的时刻：那个括号在当时的局面下无论如何都配不上对，任何合法方案都必须删掉它或某个等价位置的括号，删除数量因此不可能更少。而删掉它之后 bal 停在 0 继续扫，等于当它从没出现过，不牵连任何本来合法的括号——不多删一个。

实现上有个细节要盯住：判定多余的那个括号直接删掉、bal 保持原样不减，等于当它从未出现，绝不能让 bal 落到负数再继续。若放任 bal 变成负数往下走，后面本来合法的右括号会被连累着误判成多余，越删越多。

复杂度、边界与题目变体

时间 O(n)：正反各一遍线性扫描，每个字符只看常数次；空间 O(n)，用一个字符数组标记删除位并拼出结果。易错点除了 bal 忘归零，还有把字母也计入 bal——字母不影响配对，混进计数会把平衡算错，它们只需原样保留。

变体上，如果题目要求返回所有删除数最少的合法方案，两遍贪心就不够了：得先算出左右括号各需删几个，再用 BFS 或 DFS 枚举删哪些位置并去重校验。本题这套线性扫描的价值在于用 O(n) 拿到一个合法解，是面试里性价比极高的起手式。

Python

def removeInvalid(s):
    arr = list(s)
    def scan(idx, op, cl):          # idx 顺序, op 开括号, cl 闭括号
        bal = 0
        for i in idx:
            if arr[i] == op: bal += 1
            elif arr[i] == cl:
                if bal > 0: bal -= 1
                else: arr[i] = ''      # 多余,删除
    scan(range(len(arr)), '(', ')')    # 第一遍 删多余 )
    scan(reversed(range(len(arr))), ')', '(')  # 第二遍 删多余 (
    return ''.join(arr)

C++

string removeInvalid(string s){
    auto scan=[&](bool fwd,char op,char cl){
        int bal=0, n=s.size();
        for(int k=0;k<n;k++){
            int i = fwd ? k : n-1-k;
            if(s[i]==op) bal++;
            else if(s[i]==cl){ if(bal>0) bal--; else s[i]='*'; }
        }
    };
    scan(true,'(',')'); scan(false,')','(');
    string r; for(char c:s) if(c!='*') r+=c; return r;
}

Java

String removeInvalid(String s){
    char[] a = s.toCharArray();
    scan(a, true,  '(', ')');   // 第一遍 删多余 )
    scan(a, false, ')', '(');   // 第二遍 删多余 (
    StringBuilder r = new StringBuilder();
    for (char c : a) if (c != 0) r.append(c);
    return r.toString();
}
void scan(char[] a, boolean fwd, char op, char cl){
    int bal = 0, n = a.length;
    for (int k = 0; k < n; k++){
        int i = fwd ? k : n-1-k;
        if (a[i]==op) bal++;
        else if (a[i]==cl){ if(bal>0) bal--; else a[i]=0; }
    }
}