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

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

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

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

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