B3758 [信息与未来 2021] 括号序列

chen_zhe · 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|) 的时间复杂度下完成这一题。