小欧的括号嵌套
小欧的括号嵌套
OPPO 笔试真题 · 2024 秋招 · 后端岗
判题请到牛客原题提交。
题目描述
小欧想要构造一个合法的括号序列满足以下条件：
1.括号序列长度恰好为。
2.括号序列的嵌套层数最大值为。
括号嵌套层数是指在一个字符串中，以左括号 "(" 和右括号 ")" 形成的括号对的最大嵌套深度。
例如，在字符串 "((())())" 中，括号嵌套层数最大值为 3。
输入格式
一行两个整数。
输出格式
一行一个字符串表示括号序列。若有多种构造方案，输出任意一个即可。
示例
示例 1
输入：
3 2输出：
()(())解题思路
第一步：理解问题本质
「长度恰好为 2n 的合法括号序列」等价于：有 n 个 ( 和 n 个 )，并且任意前缀里( 的数量都不少于 )。
「嵌套层数」= 从左往右扫时深度（遇到 ( 加一、遇到 ) 减一）的最大值。
题目要求这个最大值恰好等于 r。
第二步：先造一个深度为 r 的块
最简单能控制深度的结构是一串连续的左括号接一串连续的右括号：
"(" * r + ")" * r它的深度从 1 一路上升到 r，再一路降回 0，最大值正好是 r，长度 2r。
第三步：剩下的括号对往哪放
一共 n 对，已经用掉 r 对，还剩 n − r 对。把它们平铺成 ()：
"()" * (n - r)每一对自成一层，深度只到 1，不会把总深度推到 r 以上（r ≥ 1，所以 1 ≤ r）。
把两段拼接起来，整体是「两个合法括号块首尾相连」，因此仍然合法：
任何前缀的右括号都不多于左括号，最终深度回到 0，长度 2r + 2(n − r) = 2n，深度最大值就是 r。
本题是构造 + 特判，输出任意一个合法答案都算通过，不必和样例输出一模一样。
完整代码实现
import sys
def solve() -> None:
"""先搭一个深度为 r 的块，剩下的对括号平铺"""
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
r = int(data[1])
# "("*r + ")"*r 深度恰好到 r；剩下的 n-r 对 "()" 深度只有 1
ans = "(" * r + ")" * r + "()" * (n - r)
sys.stdout.write(ans + "\n")
if __name__ == "__main__":
solve()示例推演
输入 n = 3, r = 2：
| 组成部分 | 内容 | 长度 | 这一段的最大深度 |
|---|---|---|---|
| 深度块 | (()) | 4 | 2 |
| 平铺部分 | () | 2 | 1 |
| 拼接结果 | (())() | 6 = 2 × 3 | 2 |
逐字符看深度：
| 字符 | ( | ( | ) | ) | ( | ) |
|---|---|---|---|---|---|---|
| 深度 | 1 | 2 | 1 | 0 | 1 | 0 |
最大深度 2，恰好等于 r；长度 6 = 2n；深度从未变负，结尾回到 0 —— 合法。
（题面给出的 ()(()) 同样合法，两者都对。）
再看两个边界：
n = 5, r = 1：深度块是()，平铺部分是()()()()，拼成()()()()()，深度始终不超过 1。n = 4, r = 4：平铺部分是空串，答案是(((())))，深度一路到 4。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 深度块 + 平铺 | O(n) | O(n) | 推荐，拼串本身要写 2n 个字符 |
| 输出 + 校验 | O(n) | O(1) | 额外空间只有计数器 |
易错点总结
1. 把 n 当成字符数
题目里 n 是括号对的个数，串长是 2n。写成 "("*n 就少了半截。
2. r = n 时多输出东西
此时 "()" * (n - r) 是空串，直接拼上去就行；不要额外加空格或换行分隔。
3. 深度块的顺序写反
必须先写 r 个 ( 再写 r 个 )。写成 ")("*r 前缀立刻变负，不是合法序列。
4. 拿样例输出当唯一答案
这是构造题，判题器会单独校验合法性，(())() 和 ()(()) 都会通过。
5. 拼接后忘了检查合法性
两个合法括号块首尾相接一定合法，但如果是自己另想的构造（比如先平铺再放深块），
要确认前缀和不会变负。
扩展思考
- 要求深度恰好为 r 且字典序最小：
((...))开头的构造已经是最小的了，
因为字典序上(比)小，把深的块放前面最划算。 - 要求每一层恰好出现 k 次：就变成「按层数分配括号」的问题，需要保证每层都有足够的开合。
- 计数问题：长度 2n 的合法括号序列总数是第 n 个卡特兰数
；本题问的是构造，不是计数。 - 换个角度：深度为 r 的块等价于「栈的最大高度为 r」，这也是后面做括号匹配、单调栈类题目的基础直觉。