LeetCode-Go 题解：1249. Minimum Remove to Make Valid Parentheses —— 最小删除括号使字符串有效

LeetCode-Go 题解：1249. Minimum Remove to Make Valid Parentheses —— 最小删除括号使字符串有效

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南围绕 LeetCode 第 1249 题「Minimum Remove to Make Valid Parentheses」展开，以 LeetCode-Go 仓库中该题的 README.md 为核心骨架，结合仓库内 解题源码 与 单元测试 进行源码级剖析。读完本文，你将掌握：括号字符串有效性的形式化定义、三种 O(n) 解题思路（栈、双次遍历、单次遍历 + 逆序清理）的推导过程，以及仓库实现中"一次遍历过滤多余右括号、逆序清理多余左括号"这一经典技巧的逐行原理，并能独立写出可运行的 Go 实现。

题目回顾

给定一个由'('、')'和小写英文字符组成的字符串s，任务是删除最少数量的括号（可以是'('或')'，位置任意），使得剩余的"括号字符串"有效，并返回任意一个合法字符串。

其中，括号字符串有效当且仅当满足以下任意一条：

• 它是空字符串，或只包含小写字符；
• 它可以写作AB（即A连接B），其中A和B都是有效字符串；
• 它可以写作(A)，其中A是有效字符串。

示例

约束条件

• 1 <= s.length <= 10^5
• s[i]是'('、')'或小写英文字母之一。

数据规模达到 10^5，意味着任何 O(n²) 的暴力删除方案（例如每删一个括号就重建一次字符串）都会超时，必须设计 O(n) 的单遍或双遍扫描算法。

题目大意

给定由'('、')'和小写字母组成的字符串s，需要从中删除最少数目的'('或')'（可删除任意位置的括号），使剩余的"括号字符串"有效，返回任意一个合法字符串。有效"括号字符串"满足以下任意一条：

• 空字符串，或只包含小写字母的字符串；
• 可写作AB（A连接B）的字符串，其中A、B都是有效"括号字符串"；
• 可写作(A)的字符串，其中A是有效"括号字符串"。

注意题目要求的是"最少数目的删除"，但答案不唯一，只要删除数量达到最少即可，返回任意一组合法结果都会被判为正确。

解题思路总览

原文档给出了由浅入深的三层思路，复杂度均为 O(n)，但实现复杂度逐层降低：

下面逐一展开。

方法一：栈（Stack）判断括号匹配

最容易想到的思路是借助栈判断括号匹配是否有效，思路可行，时间复杂度也是 O(n)。具体做法：

1. 正向遍历s，维护一个栈：
   • 遇到'('时，将其下标压栈；
   • 遇到')'时，若栈顶存在'('，则弹栈完成一次匹配；否则说明这是一个多余的右括号，需要删除；
   • 遇到普通小写字母，直接保留。
2. 遍历结束后，栈中剩余的下标对应的'('都是找不到右括号配对的左括号，需要删除。
3. 用哈希集合记录所有需要删除的下标，最后一次性重建字符串。

该方案直观、不易出错，但需要额外的栈空间与下标集合，代码量相对较大。

方法二：两次循环标记法（不用栈）

不用栈，可以 2 次循环遍历：

• 正向遍历一次，标记出多余的'('：用一个计数器opens，遇到'('自增；遇到')'时若opens == 0说明右括号多余（标记删除），否则opens--。
• 逆向遍历一次，再标记出多余的')'：用计数器closes，遇到')'自增；遇到'('时若closes == 0说明左括号多余（标记删除），否则closes--。
• 最后将所有这些标记多余的字符删掉即可。

这种解法写出来的代码也很简洁，时间复杂度同样是 O(n)。它不再依赖栈，仅用两个计数器加一个标记数组，空间复杂度仍为 O(n)（标记数组），但思路非常清晰，适合面试时快速给出正确解。

方法三：一次遍历 + 逆序清理（本仓库采用的实现）

针对上面的解法再改进一点：正向遍历的时候不仅标记出多余的'('，还可以顺手把多余的')'直接删除，这样只用循环一次；最后再删除掉多余的'('即可。时间复杂度依旧是 O(n)，且空间开销降为 O(1)（仅一个计数器，不含结果字符串本身的 O(n)）。

这是 LeetCode-Go 仓库实际采用的最终方案，源码见 leetcode/1249.Minimum-Remove-to-Make-Valid-Parentheses/1249. Minimum Remove to Make Valid Parentheses.go。

仓库源码逐行解析

仓库中minRemoveToMakeValid的完整实现如下（与 README 中的代码一致）：

package leetcode func minRemoveToMakeValid(s string) string { res, opens := []byte{}, 0 for i := 0; i < len(s); i++ { if s[i] == '(' { opens++ } else if s[i] == ')' { if opens == 0 { continue } opens-- } res = append(res, s[i]) } for i := len(res) - 1; i >= 0; i-- { if res[i] == '(' && opens > 0 { opens-- res = append(res[:i], res[i+1:]...) } } return string(res) }

下面拆解这段代码的每一部分。

第一遍：正向扫描，过滤多余的右括号

res, opens := []byte{}, 0 for i := 0; i < len(s); i++ { if s[i] == '(' { opens++ } else if s[i] == ')' { if opens == 0 { continue } opens-- } res = append(res, s[i]) }

• res保存"暂时合法"的字符序列，opens统计尚未配对的左括号数量。
• 遇到'('：opens++，并加入res（先不判定其是否会多余）。
• 遇到')'：
  • 若opens == 0，说明当前右括号没有任何左括号可以与它配对，它必然是多余的，直接continue跳过，即"顺手删除多余的')'"；
  • 否则opens--，表示消耗掉一个左括号完成匹配，并将该右括号加入res。
• 遇到小写字母：无条件加入res。

关键点在于：右括号的删除在正向遍历中即可就地完成，无需标记数组。左括号则暂时全部保留，等待第二遍处理。

第二遍：逆序清理多余的左括号

for i := len(res) - 1; i >= 0; i-- { if res[i] == '(' && opens > 0 { opens-- res = append(res[:i], res[i+1:]...) } }

第一遍结束时，opens里记录的就是所有没被配对的左括号数量。这些左括号都多于所需，必须删除。逆向遍历时：

• 每遇到一个'('且opens > 0，说明它属于多余的左括号，将其从res中移除，并让opens--递减；
• 当opens减到 0，说明多余的左括号已全部清理完毕，剩下的'('都是有效配对的，保留不动。

这里用到了 Go 切片删除元素的惯用写法res = append(res[:i], res[i+1:]...)，其本质是把切片在i处断开、将右半段拼接到左半段之后。注意：该操作的时间复杂度是 O(n) 级别（涉及元素搬移），但整体上所有删除操作累计仍为 O(n)，因为每个字符最多被搬移常数次。

为什么逆向删除是对的？

正向遍历中，opens计数器天然保证"当前已出现但尚未配对的左括号数量"。如果一个'('在正向扫描结束时仍未被消耗，说明它右侧不存在能与它配对的右括号（要么被提前删掉了，要么数量不够），因此它必然是多余的——这与括号"后进先出"的匹配语义完全一致，逆序清理时按从右到左的顺序删掉opens个'('即可保证删除数量最少且结果合法。

一个推演示例

以s = "a)b(c)d"为例：

• 第一遍：a入res；遇到')'时opens == 0，跳过（删除）；随后( c )正常匹配并入res；d入res。得到res = "ab(c)d"，opens = 0。
• 第二遍：opens == 0，无需清理任何左括号。
• 返回"ab(c)d"，与题目示例 2 一致。

再以s = "(a(b(c)d)"为例：

• 第一遍：三个'('依次使opens变为 3、2、1（第二个、第三个'('各自有右括号匹配，但计数器是净统计）；最终opens = 1，res = "(a(b(c)d)"。
• 第二遍：逆序扫描，第一个遇到的'('（最内层）满足opens > 0，删除并使opens = 0；继续扫描，剩余两个'('时opens == 0，保留。
• 返回"a(b(c)d)"，与题目示例 4 一致。

复杂度分析

• 时间复杂度：O(n)，其中n = len(s)。第一遍扫描每个字符恰好一次；第二遍逆序扫描长度不超过 n 的res，其中切片删除操作累计搬移的字符总量为 O(n)。整体线性。
• 空间复杂度：O(n)（结果切片res本身）。相比方法一、方法二额外需要 O(n) 的栈或标记数组，本实现除结果外仅用一个int计数器opens，辅助空间为 O(1)。

对于1 <= s.length <= 10^5的约束，O(n) 的时间复杂度在 Go 下毫秒级即可完成，完全满足题目时限。

测试用例验证

仓库为该题配套了完整的单元测试，见 leetcode/1249.Minimum-Remove-to-Make-Valid-Parentheses/1249. Minimum Remove to Make Valid Parentheses_test.go。测试文件将题目中的 4 个示例全部纳入用例：

qs := []question1249{ {para1249{"lee(t(c)o)de)"}, ans1249{"lee(t(c)o)de"}}, {para1249{"a)b(c)d"}, ans1249{"ab(c)d"}}, {para1249{"))(("}, ans1249{""}}, {para1249{"(a(b(c)d)"}, ans1249{"a(b(c)d)"}}, }

其中：

• "lee(t(c)o)de)"验证"末尾多余右括号"的删除；
• "a)b(c)d"验证"开头多余右括号"的删除；
• "))(("验证极端情况——所有括号都多余，删除后为空字符串（空串同样有效）；
• "(a(b(c)d)"验证"多余左括号"的删除（本用例正是靠第二遍逆序清理完成的）。

测试通过Test_Problem1249遍历用例并打印输入输出，可直接运行验证：

go test ./leetcode/1249.Minimum-Remove-to-Make-Valid-Parentheses/ -run Test_Problem1249 -v

整个仓库还通过 gotest.sh 以-covermode=atomic生成覆盖全部包的覆盖率文件coverage.txt，与 LeetCode-Go 项目"100% 测试覆盖率"的目标保持一致，你可以用同样的方式验证本题的实现与测试：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

边界情况与易错点

1. 全括号无效输入：如"))(("，正向扫描会删除全部右括号，逆序清理会删除全部左括号，最终返回空串——注意不要误判为空串不合法，题目明确"空字符串也是有效的"。
2. 连续多个多余左括号：如"((("，第一遍opens累积到 3，第二遍需逆序删除恰好 3 个'('，删除顺序不影响正确性，但逆序删除可以避免漏删。
3. 删除后顺序保持不变：所有删除操作都是"就地剔除"，不改变剩余字符的相对顺序，因此"a)b(c)d"不会变成"ab(cd)"之类的错序结果。
4. 切片删除的副作用：res = append(res[:i], res[i+1:]...)会修改底层数组，但由于本题是单向删除且不再依赖被覆盖的旧值，使用是安全的；理解这一点有助于避免在更复杂的场景中踩坑。
5. 字母与括号混合：小写字母永远不参与匹配判断，必须无条件保留，第一遍循环中的res = append(res, s[i])对所有非')'且非'('的字符同样生效，这是代码简洁性的来源之一。

同类题目延伸

括号类问题在 LeetCode-Go 仓库中有一整条练习主线，可与本题对照学习：

• 0020. Valid Parentheses：最经典的栈匹配入门题，是本题方法一的基础；
• 0921. Minimum Add to Make Parentheses Valid：与本题互为镜像——本题是"删除最少括号"，921 是"添加最少括号"，两者都可用计数器 O(n) 解决，921 的结论是"栈里剩下的括号数量即最少添加数"；
• 0301. Remove Invalid Parentheses：进阶版，要求返回所有可能的删除结果，需要 BFS 或 DFS 穷举；
• 0032. Longest Valid Parentheses：将"有效性"从删除问题延伸到最长连续有效子串问题，涉及动态规划或栈；
• 0022. Generate Parentheses：括号类问题的反向题——给定括号对数，生成所有有效组合。

建议按"栈匹配 → 最小删除/最小添加 → 全部删除方案 → 最长有效子串"的顺序练习，可以系统性地吃透括号匹配这一类题的核心套路：用一个计数器或栈维护"未配对左括号"的数量，结合正向/逆向扫描在 O(n) 内完成判定与修正。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go