自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:14:52，当前版本为作者最后更新于2025-03-09 13:53:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

欢迎报名洛谷网校，期待和大家一起进步！

本题考察贪心、括号匹配。

如果遇到左括号，我们直接添加到答案字符串中。而如果遇到右括号：

• 如果有左括号能够和右括号匹配，那么可以直接添加右括号；
• 如果不存在左括号匹配右括号，则需要插入一个左括号，与这个右括号匹配。

参考代码：

for (int i = 0; i < s.size(); i++) {
    char c = s[i];
    if (c == '(') { // 左括号：直接添加
        res += '(';
        left++;
    } else { // 右括号：尝试配对
        if (left == 0) {
        // 无法配对，补一个左括号和右括号
            res += "()";
        } else {
        // 可以配对，直接添加右括号
            res += ')';
            left--;
        }
    }
}

这样操作完毕后，如果还遇到有一些多余的左括号，就需要在最后补足右括号，使得其与左括号恰好配对上。

while (left > 0) {
    res += ')';
    left--;
}

这样，就可以在 $O(|S|)$ 的时间复杂度下完成这一题。