LeetCode 1249. 移除无效的括号

2026-02-04 HGNULB 约 5 分钟

文章信息 9 个分类 2 个标签

分类

题目描述

✅ 1249. 移除无效的括号

题意分析

字符串里混着小写字母和圆括号，要求删掉尽可能少的括号，让剩下的括号序列合法。字母一个都不能删，删除的对象只有括号。答案只要求返回任意一个合法结果，不需要枚举所有可能。

「合法括号序列」这个条件可以拆成两条彼此独立的性质：从左往右扫的任意时刻，已出现的右括号数量都不能超过左括号；扫完全串后左右括号数量必须相等。这两条一起充要地刻画了合法性，也正好对应两类必须删除的括号——扫描途中就找不到配对的右括号，以及扫描结束仍未被配对的左括号。

约束信号是「删最少」。既然不合法的位置是被唯一确定的（下面会说清为什么），就不存在选择空间，也就不需要搜索或 DP。

边界情形：字符串可能完全没有括号，此时原样返回；可能全是括号且完全非法（例如 "))(("），此时删成空串；也可能本来就合法，一个都不删。

解法：栈标记无效括号位置

核心思路

有效括号要求每个右括号都能与左侧尚未匹配的左括号配对，并且扫描结束后不能剩下左括号。用栈保存未匹配左括号的下标：

遇到 ( 时压入下标；

遇到 ) 时，栈非空就弹出一个左括号完成配对，否则当前右括号必须删除；

扫描结束后，栈内下标都是必须删除的多余左括号。

用布尔数组标记这些位置，再按原顺序重建答案。这样保留所有普通字符，也不依赖某一个唯一答案。

不变量：扫描到位置 i 后，栈中恰好保存此前尚未匹配的左括号；已标记的右括号在其左侧不存在可用配对，因此任何有效结果都必须删除它。

解题步骤

创建下标栈和长度为 n 的删除标记数组。

从左向右扫描：左括号入栈；右括号优先与栈顶配对，无法配对则标记删除。

扫描结束后，把栈中剩余左括号下标全部标记删除。

再扫描一次原串，跳过标记位置并拼接其余字符。

例如 a)b(c)d 中，第一个 ) 左侧无可用左括号，必须删除；其余括号能配对，结果为 ab(c)d。

代码实现

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public String minRemoveToMakeValid(String s) {
        boolean[] remove = new boolean[s.length()];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            char current = s.charAt(i);
            if (current == '(') {
                stack.push(i);
            } else if (current == ')') {
                if (stack.isEmpty()) {
                    remove[i] = true;
                } else {
                    stack.pop();
                }
            }
        }

        while (!stack.isEmpty()) {
            remove[stack.pop()] = true;
        }

        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (!remove[i]) {
                answer.append(s.charAt(i));
            }
        }
        return answer.toString();
    }
}

func minRemoveToMakeValid(s string) string {
    remove := make([]bool, len(s))
    stack := make([]int, 0)

    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            stack = append(stack, i)
        } else if s[i] == ')' {
            if len(stack) == 0 {
                remove[i] = true
            } else {
                stack = stack[:len(stack)-1]
            }
        }
    }

    for _, index := range stack {
        remove[index] = true
    }

    answer := make([]byte, 0, len(s))
    for i := 0; i < len(s); i++ {
        if !remove[i] {
            answer = append(answer, s[i])
        }
    }
    return string(answer)
}

复杂度分析

时间复杂度：$O(n)$。两次线性扫描，每个括号下标最多入栈、出栈一次。

空间复杂度：$O(n)$。栈、删除标记和返回结果最坏都与字符串等长。

关键点总结

栈保存未匹配左括号的下标，便于最后精确删除。

无匹配左括号的右括号当场确定无效；剩余左括号在扫描结束后确定无效。

题目允许多个答案，算法只需保证删除数量最少且结果有效。

普通字符不参与匹配，重建时必须原样保留。

易错点总结

只删除多余右括号：扫描结束后栈中残留的左括号也必须删除。

遇到右括号就弹栈：栈为空时会越界，而且该右括号本身应被删除。

栈只存字符不存位置：最后无法确定应跳过原串中的哪一个左括号。

重建时只保留字母：题目允许的非括号字符都应原样保留。

要求得到唯一字符串：最少删除结果可能不唯一，任意合法结果都可接受。

相似题目

题目	难度	考察点
20. 有效的括号	简单	只做合法性判定，且要处理三种括号类型
32. 最长有效括号	困难	用栈底哨兵下标求最长连续合法段的长度
301. 删除无效的括号	困难	要输出所有最少删除方案，需 BFS 或带剪枝回溯
678. 有效的括号字符串	中等	多出通配符 `*`，改用左右计数的可行区间
1614. 括号的最大嵌套深度	简单	输入保证合法，只需跟踪计数器的最大值