LeetCode-Go 题解 | 1021. Remove Outermost Parentheses移除最外层括号计数法 栈模拟【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 1021.Remove-Outermost-Parentheses 题目文档 展开完整讲解「移除最外层括号」这道经典栈/计数题先弄清「有效括号串」与「原始串primitive」的定义再结合仓库中两版 Go 实现逐步推导如何用计数器与显式栈两种思路剥离每个原始段的最外层括号。读完本文你将掌握这类按括号深度切分子串题目的通用解法与复杂度分析方法并能直接运行仓库内的测试用例验证结果。题目原文与目标题目要求给定一个有效括号字符串S将其拆分为若干个原始primitive有效括号串后把每个原始串的最外层括号去掉再拼接返回结果。例如S (()())(())原始分解为(()()) (())各自去掉最外层后得到()() ()最终返回()()()。题目约束见 README.mdS.length 10000S[i]只能是(或)S一定是有效括号字符串无需额外校验输入合法性由于输入保证有效解题时不需要处理非法括号串的防御逻辑可以专注在如何定位每个原始串的边界这一个核心问题上。核心概念有效括号串与原始串原题文档给出了两个关键定义有效括号字符串Valid Parentheses String空串、形如( A )其中 A 为有效串、或A BA、B 均为有效串构成的字符串。例如、()、(())()、(()(()))都是有效括号串。原始串Primitive非空的、且无法再拆分成两个非空有效括号串拼接的有效括号串。简单说原始串就是括号深度从 0 到 1中间回落但永不小于 1最后再回到 0的不可再分片段如()、(())、(()())。给定有效串S后它的原始分解是唯一的S P_1 P_2 ... P_k其中每个P_i都是原始串。本题要做的就是对每个P_i去掉最外层括号一个(和一个)保留中间部分并拼接。解题思路用计数代替栈模拟README 的解题思路一句话点破核心——用栈模拟即可扫描字符串维护当前括号深度每当深度归零就说明一个完整的原始段结束此时把该段掐头去尾去掉最外层括号加入答案。进一步抽象栈的核心能力其实只是一个深度计数器(使深度 1)使深度 -1。由于题目只关心当前处于第几层完全可以用一个整数计数器替代真正的栈容器这就是仓库中解法一的思路。解法一计数器 切片拼接仓库第一版实现位于 1021. Remove Outermost Parentheses.go// 解法一 func removeOuterParentheses(S string) string { now, current, ans : 0, , for _, char : range S { if string(char) ( { now } else if string(char) ) { now-- } current string(char) if now 0 { ans current[1 : len(current)-1] current } } return ans }执行流程拆解维护三个变量now当前括号深度、current正在积累的原始段、ans最终答案逐字符扫描S遇到(深度 1遇到)深度 -1并把当前字符追加进current当now 0时说明current恰好构成一个完整的原始串执行current[1 : len(current)-1]去掉首尾括号后拼入ans并清空current开始下一段。以(()())(())为例跟踪过程已扫描前缀nowcurrent动作(1(继续积累((2((继续积累(()1(()继续积累(()(2(()(继续积累(()()1(()()继续积累(()())0(()())切出()()加入答案清空(()())(1(继续积累(()())((2((继续积累(()())(()1(()继续积累(()())(())0(())切出()加入答案最终答案()() () ()()()与示例 1 完全一致。正确性要点因为输入保证是有效括号串深度一定不会出现负数且必然以深度 0 结束深度归零的时机恰好就是原始段的结束边界不会出现多切或漏切current[1 : len(current)-1]利用 Go 字符串切片特性一次性丢弃段首的(与段尾的)而中间内容可能包含多层嵌套被原样保留。复杂度分析时间复杂度O(n)单次线性扫描n为S长度空间复杂度O(n)current与ans在最坏情况下累计存储接近n个字符例如()()()...这类串每段都只有 2 个字符去掉外层后几乎全被丢弃实际存储量上界仍为O(n)。解法二显式栈模拟仓库还提供了第二版实现用真实的字节栈[]byte来模拟括号嵌套位于 1021. Remove Outermost Parentheses.go// 解法二 func removeOuterParentheses1(S string) string { stack, res, counter : []byte{}, , 0 for i : 0; i len(S); i { if counter 0 len(stack) 1 S[i] ) { stack stack[1:] continue } if len(stack) 0 S[i] ( { stack append(stack, S[i]) continue } if len(stack) 0 { switch S[i] { case (: { counter res ( } case ): { counter-- res ) } } } } return res }与解法一的差异用一个[]byte栈记录当前处于第几层原始段遇到段首(时压栈遇到与之匹配的段尾)时弹栈counter记录当前段内的嵌套深度只有len(stack) 0即已经在某个原始段内部时才把字符写入结果res因此最外层括号段首(和段尾)永远不会进入res天然完成了移除最外层的工作无需像解法一那样事后切片。两种解法的核心逻辑等价解法一是先攒段、后掐头去尾解法二是在段内时直接放行、段边界直接跳过。从源码结构看解法二更贴近 README 中用栈模拟的字面描述而解法一在代码量上更精简。两版函数都定义在同一个包内分别命名为removeOuterParentheses与removeOuterParentheses1可以对照阅读。测试验证三个示例全覆盖仓库为该题编写了完整的表驱动测试位于 1021. Remove Outermost Parentheses_test.go覆盖了 README 中的全部三个示例输入期望输出覆盖点(()())(())()()()多段原始串的拼接(()())(())(()(()))()()()()(())含嵌套较深段(()(()))→()(())的混合场景()()每段均为最小原始串()去外层后全空测试通过Test_Problem1021统一驱动循环中同时调用removeOuterParentheses并执行removeOuterParentheses1保证两个版本行为一致。其中第三个用例是最容易出错的边界()本身就是原始串去掉最外层后为空串若实现没有正确处理段长度为 2的情况就会在这里产生多余的括号。如需本地运行验证可在仓库根目录执行go test -v ./leetcode/1021.Remove-Outermost-Parentheses/...该目录为独立子包测试文件与解法文件同属leetcode包可直接针对该用例目录运行。从源码结构看本题的推广价值移除最外层括号是一类按括号深度切分问题的入门代表其思想可以推广到同类型题目按深度切分本题依赖深度归零 原始段边界同样的计数器模式可用于统计括号最大嵌套深度、配对括号等问题只处理段内内容解法二的栈非空才写入结果思路本质上是一种忽略最外层包裹层的过滤模式可迁移到需要剥离最外层包裹结构的解析场景计数器替代栈当栈中元素只需记录层数时int计数器就是最轻量的实现这也是 Go 面试中常见的优化点。仓库中其他括号类题目的解法文件如 0020.Valid-Parentheses、0856.Score-of-Parentheses也大量运用栈与计数器可与本题对照学习形成体系。小结本题的核心是找到每个原始段的边界深度从 0 升到 1 是段起点深度回到 0 是段终点仓库解法一用计数器 字符串切片实现代码最简洁解法二用显式字节栈模拟更贴近栈模拟的原意两者复杂度均为O(n)时间、O(n)空间三个示例含()()边界用例已由仓库内的表驱动测试覆盖可直接运行验证。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解 | 1021. Remove Outermost Parentheses：移除最外层括号（计数法 + 栈模拟）
LeetCode-Go 题解 | 1021. Remove Outermost Parentheses移除最外层括号计数法 栈模拟【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 1021.Remove-Outermost-Parentheses 题目文档 展开完整讲解「移除最外层括号」这道经典栈/计数题先弄清「有效括号串」与「原始串primitive」的定义再结合仓库中两版 Go 实现逐步推导如何用计数器与显式栈两种思路剥离每个原始段的最外层括号。读完本文你将掌握这类按括号深度切分子串题目的通用解法与复杂度分析方法并能直接运行仓库内的测试用例验证结果。题目原文与目标题目要求给定一个有效括号字符串S将其拆分为若干个原始primitive有效括号串后把每个原始串的最外层括号去掉再拼接返回结果。例如S (()())(())原始分解为(()()) (())各自去掉最外层后得到()() ()最终返回()()()。题目约束见 README.mdS.length 10000S[i]只能是(或)S一定是有效括号字符串无需额外校验输入合法性由于输入保证有效解题时不需要处理非法括号串的防御逻辑可以专注在如何定位每个原始串的边界这一个核心问题上。核心概念有效括号串与原始串原题文档给出了两个关键定义有效括号字符串Valid Parentheses String空串、形如( A )其中 A 为有效串、或A BA、B 均为有效串构成的字符串。例如、()、(())()、(()(()))都是有效括号串。原始串Primitive非空的、且无法再拆分成两个非空有效括号串拼接的有效括号串。简单说原始串就是括号深度从 0 到 1中间回落但永不小于 1最后再回到 0的不可再分片段如()、(())、(()())。给定有效串S后它的原始分解是唯一的S P_1 P_2 ... P_k其中每个P_i都是原始串。本题要做的就是对每个P_i去掉最外层括号一个(和一个)保留中间部分并拼接。解题思路用计数代替栈模拟README 的解题思路一句话点破核心——用栈模拟即可扫描字符串维护当前括号深度每当深度归零就说明一个完整的原始段结束此时把该段掐头去尾去掉最外层括号加入答案。进一步抽象栈的核心能力其实只是一个深度计数器(使深度 1)使深度 -1。由于题目只关心当前处于第几层完全可以用一个整数计数器替代真正的栈容器这就是仓库中解法一的思路。解法一计数器 切片拼接仓库第一版实现位于 1021. Remove Outermost Parentheses.go// 解法一 func removeOuterParentheses(S string) string { now, current, ans : 0, , for _, char : range S { if string(char) ( { now } else if string(char) ) { now-- } current string(char) if now 0 { ans current[1 : len(current)-1] current } } return ans }执行流程拆解维护三个变量now当前括号深度、current正在积累的原始段、ans最终答案逐字符扫描S遇到(深度 1遇到)深度 -1并把当前字符追加进current当now 0时说明current恰好构成一个完整的原始串执行current[1 : len(current)-1]去掉首尾括号后拼入ans并清空current开始下一段。以(()())(())为例跟踪过程已扫描前缀nowcurrent动作(1(继续积累((2((继续积累(()1(()继续积累(()(2(()(继续积累(()()1(()()继续积累(()())0(()())切出()()加入答案清空(()())(1(继续积累(()())((2((继续积累(()())(()1(()继续积累(()())(())0(())切出()加入答案最终答案()() () ()()()与示例 1 完全一致。正确性要点因为输入保证是有效括号串深度一定不会出现负数且必然以深度 0 结束深度归零的时机恰好就是原始段的结束边界不会出现多切或漏切current[1 : len(current)-1]利用 Go 字符串切片特性一次性丢弃段首的(与段尾的)而中间内容可能包含多层嵌套被原样保留。复杂度分析时间复杂度O(n)单次线性扫描n为S长度空间复杂度O(n)current与ans在最坏情况下累计存储接近n个字符例如()()()...这类串每段都只有 2 个字符去掉外层后几乎全被丢弃实际存储量上界仍为O(n)。解法二显式栈模拟仓库还提供了第二版实现用真实的字节栈[]byte来模拟括号嵌套位于 1021. Remove Outermost Parentheses.go// 解法二 func removeOuterParentheses1(S string) string { stack, res, counter : []byte{}, , 0 for i : 0; i len(S); i { if counter 0 len(stack) 1 S[i] ) { stack stack[1:] continue } if len(stack) 0 S[i] ( { stack append(stack, S[i]) continue } if len(stack) 0 { switch S[i] { case (: { counter res ( } case ): { counter-- res ) } } } } return res }与解法一的差异用一个[]byte栈记录当前处于第几层原始段遇到段首(时压栈遇到与之匹配的段尾)时弹栈counter记录当前段内的嵌套深度只有len(stack) 0即已经在某个原始段内部时才把字符写入结果res因此最外层括号段首(和段尾)永远不会进入res天然完成了移除最外层的工作无需像解法一那样事后切片。两种解法的核心逻辑等价解法一是先攒段、后掐头去尾解法二是在段内时直接放行、段边界直接跳过。从源码结构看解法二更贴近 README 中用栈模拟的字面描述而解法一在代码量上更精简。两版函数都定义在同一个包内分别命名为removeOuterParentheses与removeOuterParentheses1可以对照阅读。测试验证三个示例全覆盖仓库为该题编写了完整的表驱动测试位于 1021. Remove Outermost Parentheses_test.go覆盖了 README 中的全部三个示例输入期望输出覆盖点(()())(())()()()多段原始串的拼接(()())(())(()(()))()()()()(())含嵌套较深段(()(()))→()(())的混合场景()()每段均为最小原始串()去外层后全空测试通过Test_Problem1021统一驱动循环中同时调用removeOuterParentheses并执行removeOuterParentheses1保证两个版本行为一致。其中第三个用例是最容易出错的边界()本身就是原始串去掉最外层后为空串若实现没有正确处理段长度为 2的情况就会在这里产生多余的括号。如需本地运行验证可在仓库根目录执行go test -v ./leetcode/1021.Remove-Outermost-Parentheses/...该目录为独立子包测试文件与解法文件同属leetcode包可直接针对该用例目录运行。从源码结构看本题的推广价值移除最外层括号是一类按括号深度切分问题的入门代表其思想可以推广到同类型题目按深度切分本题依赖深度归零 原始段边界同样的计数器模式可用于统计括号最大嵌套深度、配对括号等问题只处理段内内容解法二的栈非空才写入结果思路本质上是一种忽略最外层包裹层的过滤模式可迁移到需要剥离最外层包裹结构的解析场景计数器替代栈当栈中元素只需记录层数时int计数器就是最轻量的实现这也是 Go 面试中常见的优化点。仓库中其他括号类题目的解法文件如 0020.Valid-Parentheses、0856.Score-of-Parentheses也大量运用栈与计数器可与本题对照学习形成体系。小结本题的核心是找到每个原始段的边界深度从 0 升到 1 是段起点深度回到 0 是段终点仓库解法一用计数器 字符串切片实现代码最简洁解法二用显式字节栈模拟更贴近栈模拟的原意两者复杂度均为O(n)时间、O(n)空间三个示例含()()边界用例已由仓库内的表驱动测试覆盖可直接运行验证。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
