LeetCode-Go 题解精讲1111. Maximum Nesting Depth of Two Valid Parentheses Strings——用二分拆分最小化括号嵌套深度【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 LeetCode-Go 仓库中 1111 题文档 为骨架系统讲解「有效括号字符串VPS」的嵌套深度定义、将字符串拆分为两个 VPS 子序列以最小化max(depth(A), depth(B))的贪心与二分思路并结合仓库内两份 Go 实现源码与测试用例给出可直接复制运行的完整解法。读完你既能掌握这道经典括号类问题的两种 O(n) 解法也能理解二分平分深度这一思路背后的正确性依据。题目将括号字符串分成两个最小深度的 VPS 子序列有效括号字符串VPS的递归定义一个字符串是有效括号字符串Valid Parentheses String简称 VPS当且仅当它只由(和)构成且满足下列三个条件之一它是空字符串它可以写成ABA与B连接其中A和B都是 VPS它可以写成(A)在 VPSA外面包一层括号其中A是 VPS。基于同样的递归结构可以定义任意 VPSS的嵌套深度depth(S)depth() 0depth(A B) max(depth(A), depth(B))其中A、B都是 VPSdepth(( A )) 1 depth(A)其中A是 VPS。例如、()()、()(()())都是 VPS嵌套深度分别为 0、1、2而)(与(()都不是 VPS。问题目标与输出编码给定一个 VPS 字符串seq把它拆成两个不相交的子序列A和B要求A、B各自都是 VPS且A.length B.length seq.length。在所有这些拆分方案中选取使max(depth(A), depth(B))取值最小的一组。返回一个长度为seq.length的答案数组answer编码规则为若seq[i]属于A则answer[i] 0否则answer[i] 1。即使存在多个满足要求的答案只需返回任意一个。示例 1Input: seq (()()) Output: [0,1,1,1,1,0]示例 2Input: seq ()(())() Output: [0,0,0,1,1,0,1,1]约束条件1 seq.size 10000解题思路让 A、B 的深度尽量扁平本题的核心矛盾是seq本身可能有很深的嵌套我们要把它摊平到两个组里使两组中较深的那一组尽可能浅。原文档给出了两条互为表里的思路思路一贪心 / 交替如果 A 部分和 B 部分都尽快完成括号匹配、避免深层次嵌套那么总层次就会变小。具体做法是让嵌套中属于 A 的括号与属于 B 的括号间隔排列。例如(((())))的嵌套深度是 4按照该贪心思想标记为0101 1010——同一层的左右括号分给同一组相邻深度的括号分给不同组于是每个组内的最大嵌套深度都被压到约一半。思路二二分平分深度把深度平均分给 A 部分和 B 部分。分两步第一次遍历用计数器算出整个字符串的最大嵌套深度第二次遍历把深度小于等于最大深度一半的括号标记为 0分给 A其余标记为 1分给 B。两条思路殊途同归无论按奇偶层交替思路一还是按前一半层 / 后一半层切分思路二都能保证max(depth(A), depth(B)) ceil(maxDepth / 2)这正好是理论下界——seq最深的那对括号必须分属某一组因此至少有一组的深度不低于ceil(maxDepth / 2)。解法一源码剖析两次遍历的二分拆分仓库在 1111. Maximum Nesting Depth of Two Valid Parentheses Strings.go 中给出了对应解法一 二分思想的实现maxDepthAfterSplit// 解法一 二分思想 func maxDepthAfterSplit(seq string) []int { stack, maxDepth, res : 0, 0, []int{} for _, v : range seq { if v ( { stack maxDepth max(stack, maxDepth) } else { stack-- } } stack 0 for i : 0; i len(seq); i { if seq[i] ( { stack if stack maxDepth/2 { res append(res, 0) } else { res append(res, 1) } } else { if stack maxDepth/2 { res append(res, 0) } else { res append(res, 1) } stack-- } } return res }第一遍用计数器求最大深度用一个整型计数器stack模拟括号层数遇到(加一、遇到)减一同时用max(stack, maxDepth)记录历史峰值。因为seq保证是 VPS计数器最终归零。这一遍的时间复杂度为 O(n)且只占用 O(1) 辅助空间。第二遍按当前深度 ≤ maxDepth/2切分第二遍重新从stack 0开始扫描遇到(先stack再判断stack maxDepth/2成立标 0A否则标 1B遇到)在stack--之前用与它配对的左括号相同的深度值做判断因此左右括号会得到相同标记——这是关键它保证了 A、B 各自仍然是 VPS成对括号不会拆散。以示例(()())为例深度序列为 1,2,2,2,2,1maxDepth 2maxDepth/2 1于是深度为 1 的两端括号标 0、深度为 2 的中间四括号标 1得到[0,1,1,1,1,0]与题目示例 1 完全一致。同理()(())()的深度序列为 1,1,1,2,2,1,1,1切分后得到[0,0,0,1,1,0,1,1]与示例 2 一致。注意maxDepth/2是整数除法等价于floor(maxDepth/2)。当最大深度为奇数时B 组会多承载一层深度为ceil(maxDepth/2)这仍然是最优值因为奇数深度无法被两个组完美平分。解法二源码剖析单次遍历的奇偶交替模拟同一文件中还提供了解法二 模拟的实现maxDepthAfterSplit1它用显式栈一次遍历完成思路正是原文档的贪心间隔排列// 解法二 模拟 func maxDepthAfterSplit1(seq string) []int { stack, top, res : make([]int, len(seq)), -1, make([]int, len(seq)) for i, r : range seq { if r ) { res[i] res[stack[top]] top-- continue } top stack[top] i res[i] top % 2 } return res }逐行解读用数组stack充当手动栈top指向栈顶初始 -1栈内存的是尚未匹配的左括号的下标遇到(压栈并把当前位置的标签设为top % 2。由于top恰好等于该括号所处的零基深度top % 2就实现了相邻深度交替分给 A/B的贪心深度为奇偶交替的括号被轮流放入两个组遇到)直接复制其配对左括号栈顶stack[top]的标签到当前位置然后出栈。这一步与解法一成对括号同组的保证同理。以(((())))深度 4为例四个左括号深度依次为 1、2、3、4标签为 0、1、0、1四个右括号复制对应标签最终得到[0,1,0,1,1,0,1,0]正是原文档所举的0101 1010。解法二只需一次遍历但由于要记录每个左括号的下标用于回填标签辅助空间为 O(n)解法一辅助空间为 O(1)。两者的时间复杂度和输出数组大小完全相同。为什么按层切分必然合法且最优可以从两点论证合法性在于两种实现都保证了成对括号标签一致。若一对(...)中的左右括号同属一组那么对每组而言它内部只是若干完整括号对的拼接与有限层嵌套必然仍是 VPS最优性在于seq的最大深度maxDepth必然落在某一组内该组深度至少为ceil(maxDepth/2)而按层切分无论奇偶交替还是对半分恰好把最深括号所在组压到ceil(maxDepth/2)因此达成理论下界。这也是本题可能有多个正确答案返回任意一个即可的原因——两种解法输出的都是合法最优解只是层分配方式不同。测试用例与验证方式仓库为该题配套了单元测试 1111. Maximum Nesting Depth of Two Valid Parentheses Strings_test.goTest_Problem1111覆盖了题目的两个官方示例seq (()())期望输出[0,1,1,1,1,0]seq ()(())()期望输出[0,0,0,1,1,0,1,1]。测试对maxDepthAfterSplit的结果做了断言同时也执行了maxDepthAfterSplit1验证其可运行性。你可以通过仓库根目录的 gotest.sh 中定义的命令执行全量测试并生成覆盖率go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...或仅针对本题运行go test ./leetcode/1111.Maximum-Nesting-Depth-of-Two-Valid-Parentheses-Strings/ -v。本仓库基于 Go 1.19见 go.mod解法只依赖标准库在任何 Go 1.13 环境均可直接编译运行。小结LeetCode 1111 是一道定义驱动的括号类经典题先利用计数器求出整体最大嵌套深度再通过成对同组 按层切分把深度均摊到两个 VPS 子序列上即可把max(depth(A), depth(B))压到理论最小值ceil(maxDepth/2)。仓库中的两份实现分别演示了两次遍历的二分切分O(1) 辅助空间与单次遍历的奇偶交替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 题解精讲：1111. Maximum Nesting Depth of Two Valid Parentheses Strings——用二分拆分最小化括号嵌套深度
LeetCode-Go 题解精讲1111. Maximum Nesting Depth of Two Valid Parentheses Strings——用二分拆分最小化括号嵌套深度【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 LeetCode-Go 仓库中 1111 题文档 为骨架系统讲解「有效括号字符串VPS」的嵌套深度定义、将字符串拆分为两个 VPS 子序列以最小化max(depth(A), depth(B))的贪心与二分思路并结合仓库内两份 Go 实现源码与测试用例给出可直接复制运行的完整解法。读完你既能掌握这道经典括号类问题的两种 O(n) 解法也能理解二分平分深度这一思路背后的正确性依据。题目将括号字符串分成两个最小深度的 VPS 子序列有效括号字符串VPS的递归定义一个字符串是有效括号字符串Valid Parentheses String简称 VPS当且仅当它只由(和)构成且满足下列三个条件之一它是空字符串它可以写成ABA与B连接其中A和B都是 VPS它可以写成(A)在 VPSA外面包一层括号其中A是 VPS。基于同样的递归结构可以定义任意 VPSS的嵌套深度depth(S)depth() 0depth(A B) max(depth(A), depth(B))其中A、B都是 VPSdepth(( A )) 1 depth(A)其中A是 VPS。例如、()()、()(()())都是 VPS嵌套深度分别为 0、1、2而)(与(()都不是 VPS。问题目标与输出编码给定一个 VPS 字符串seq把它拆成两个不相交的子序列A和B要求A、B各自都是 VPS且A.length B.length seq.length。在所有这些拆分方案中选取使max(depth(A), depth(B))取值最小的一组。返回一个长度为seq.length的答案数组answer编码规则为若seq[i]属于A则answer[i] 0否则answer[i] 1。即使存在多个满足要求的答案只需返回任意一个。示例 1Input: seq (()()) Output: [0,1,1,1,1,0]示例 2Input: seq ()(())() Output: [0,0,0,1,1,0,1,1]约束条件1 seq.size 10000解题思路让 A、B 的深度尽量扁平本题的核心矛盾是seq本身可能有很深的嵌套我们要把它摊平到两个组里使两组中较深的那一组尽可能浅。原文档给出了两条互为表里的思路思路一贪心 / 交替如果 A 部分和 B 部分都尽快完成括号匹配、避免深层次嵌套那么总层次就会变小。具体做法是让嵌套中属于 A 的括号与属于 B 的括号间隔排列。例如(((())))的嵌套深度是 4按照该贪心思想标记为0101 1010——同一层的左右括号分给同一组相邻深度的括号分给不同组于是每个组内的最大嵌套深度都被压到约一半。思路二二分平分深度把深度平均分给 A 部分和 B 部分。分两步第一次遍历用计数器算出整个字符串的最大嵌套深度第二次遍历把深度小于等于最大深度一半的括号标记为 0分给 A其余标记为 1分给 B。两条思路殊途同归无论按奇偶层交替思路一还是按前一半层 / 后一半层切分思路二都能保证max(depth(A), depth(B)) ceil(maxDepth / 2)这正好是理论下界——seq最深的那对括号必须分属某一组因此至少有一组的深度不低于ceil(maxDepth / 2)。解法一源码剖析两次遍历的二分拆分仓库在 1111. Maximum Nesting Depth of Two Valid Parentheses Strings.go 中给出了对应解法一 二分思想的实现maxDepthAfterSplit// 解法一 二分思想 func maxDepthAfterSplit(seq string) []int { stack, maxDepth, res : 0, 0, []int{} for _, v : range seq { if v ( { stack maxDepth max(stack, maxDepth) } else { stack-- } } stack 0 for i : 0; i len(seq); i { if seq[i] ( { stack if stack maxDepth/2 { res append(res, 0) } else { res append(res, 1) } } else { if stack maxDepth/2 { res append(res, 0) } else { res append(res, 1) } stack-- } } return res }第一遍用计数器求最大深度用一个整型计数器stack模拟括号层数遇到(加一、遇到)减一同时用max(stack, maxDepth)记录历史峰值。因为seq保证是 VPS计数器最终归零。这一遍的时间复杂度为 O(n)且只占用 O(1) 辅助空间。第二遍按当前深度 ≤ maxDepth/2切分第二遍重新从stack 0开始扫描遇到(先stack再判断stack maxDepth/2成立标 0A否则标 1B遇到)在stack--之前用与它配对的左括号相同的深度值做判断因此左右括号会得到相同标记——这是关键它保证了 A、B 各自仍然是 VPS成对括号不会拆散。以示例(()())为例深度序列为 1,2,2,2,2,1maxDepth 2maxDepth/2 1于是深度为 1 的两端括号标 0、深度为 2 的中间四括号标 1得到[0,1,1,1,1,0]与题目示例 1 完全一致。同理()(())()的深度序列为 1,1,1,2,2,1,1,1切分后得到[0,0,0,1,1,0,1,1]与示例 2 一致。注意maxDepth/2是整数除法等价于floor(maxDepth/2)。当最大深度为奇数时B 组会多承载一层深度为ceil(maxDepth/2)这仍然是最优值因为奇数深度无法被两个组完美平分。解法二源码剖析单次遍历的奇偶交替模拟同一文件中还提供了解法二 模拟的实现maxDepthAfterSplit1它用显式栈一次遍历完成思路正是原文档的贪心间隔排列// 解法二 模拟 func maxDepthAfterSplit1(seq string) []int { stack, top, res : make([]int, len(seq)), -1, make([]int, len(seq)) for i, r : range seq { if r ) { res[i] res[stack[top]] top-- continue } top stack[top] i res[i] top % 2 } return res }逐行解读用数组stack充当手动栈top指向栈顶初始 -1栈内存的是尚未匹配的左括号的下标遇到(压栈并把当前位置的标签设为top % 2。由于top恰好等于该括号所处的零基深度top % 2就实现了相邻深度交替分给 A/B的贪心深度为奇偶交替的括号被轮流放入两个组遇到)直接复制其配对左括号栈顶stack[top]的标签到当前位置然后出栈。这一步与解法一成对括号同组的保证同理。以(((())))深度 4为例四个左括号深度依次为 1、2、3、4标签为 0、1、0、1四个右括号复制对应标签最终得到[0,1,0,1,1,0,1,0]正是原文档所举的0101 1010。解法二只需一次遍历但由于要记录每个左括号的下标用于回填标签辅助空间为 O(n)解法一辅助空间为 O(1)。两者的时间复杂度和输出数组大小完全相同。为什么按层切分必然合法且最优可以从两点论证合法性在于两种实现都保证了成对括号标签一致。若一对(...)中的左右括号同属一组那么对每组而言它内部只是若干完整括号对的拼接与有限层嵌套必然仍是 VPS最优性在于seq的最大深度maxDepth必然落在某一组内该组深度至少为ceil(maxDepth/2)而按层切分无论奇偶交替还是对半分恰好把最深括号所在组压到ceil(maxDepth/2)因此达成理论下界。这也是本题可能有多个正确答案返回任意一个即可的原因——两种解法输出的都是合法最优解只是层分配方式不同。测试用例与验证方式仓库为该题配套了单元测试 1111. Maximum Nesting Depth of Two Valid Parentheses Strings_test.goTest_Problem1111覆盖了题目的两个官方示例seq (()())期望输出[0,1,1,1,1,0]seq ()(())()期望输出[0,0,0,1,1,0,1,1]。测试对maxDepthAfterSplit的结果做了断言同时也执行了maxDepthAfterSplit1验证其可运行性。你可以通过仓库根目录的 gotest.sh 中定义的命令执行全量测试并生成覆盖率go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...或仅针对本题运行go test ./leetcode/1111.Maximum-Nesting-Depth-of-Two-Valid-Parentheses-Strings/ -v。本仓库基于 Go 1.19见 go.mod解法只依赖标准库在任何 Go 1.13 环境均可直接编译运行。小结LeetCode 1111 是一道定义驱动的括号类经典题先利用计数器求出整体最大嵌套深度再通过成对同组 按层切分把深度均摊到两个 VPS 子序列上即可把max(depth(A), depth(B))压到理论最小值ceil(maxDepth/2)。仓库中的两份实现分别演示了两次遍历的二分切分O(1) 辅助空间与单次遍历的奇偶交替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），仅供参考