小欧的括号嵌套

[题目链接](https://www.nowcoder.com/practice/0b461d2b82834cb1881567744effb0c1)

思路

构造一个由 $n$ 对括号组成的合法括号序列，使得最大嵌套深度恰好为 $k$ 。

构造方法

要让嵌套深度恰好为 $k$ ，最直接的方式是：

先写 $k$ 层嵌套：连续放 $k$ 个左括号，再连续放 $k$ 个右括号，形成 (((...)))，这部分贡献了深度为 $k$ 的嵌套。
剩余 $n - k$ 对括号：在最外层依次追加 ()，每个 () 的嵌套深度仅为 1，不会增加最大深度。

最终输出为：(((...)))()()...() ，其中前半段有 $k$ 层嵌套，后半段有 $n - k$ 个独立的 ()。

样例演示

输入 $n = 3, k = 2$ ：

先放 2 层嵌套：(())
再放 $3 - 2 = 1$ 个独立括号对：()
拼接得到 (())()，最大深度为 2

题目给出的参考答案 ()(()) 也是合法的，构造方案不唯一。

复杂度分析

时间复杂度： $O(n)$ ，拼接长度为 $2n$ 的字符串。
空间复杂度： $O(n)$ ，存储输出字符串。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, k;
    cin >> n >> k;
    string ans;
    for(int i = 0; i < k; i++) ans += '(';
    for(int i = 0; i < k; i++) ans += ')';
    for(int i = 0; i < n - k; i++) ans += "()";
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k; i++) sb.append('(');
        for (int i = 0; i < k; i++) sb.append(')');
        for (int i = 0; i < n - k; i++) sb.append("()");
        System.out.println(sb.toString());
    }
}

n, k = map(int, input().split())
print('(' * k + ')' * k + '()' * (n - k))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const [n, k] = line.trim().split(' ').map(Number);
    console.log('('.repeat(k) + ')'.repeat(k) + '()'.repeat(n - k));
    rl.close();
});