括号消除

题目描述

给定一个只含 ( 与 ) 的字符串 $S$，定义消除操作如下：
从 $S$ 的第一个字符开始，检查是否出现 ()，如果存在，则从 $S$ 中删除第一个出现的 ()，然后开始新一轮的消除操作。
若对 $S$ 进行上述消除操作，直到 $S$ 再也找不到任何 () 为止。请输出停止操作时，$S$ 还剩多少个字符。

输入格式

单个字符串表示输入的括号序列。

输出格式

单个整数表示答案。

数据范围

记 $|S|$ 表示输入字符的长度，则：

• 30% 的数据：$1\le |S|\le 100$
• 100% 的数据：$1\le |S|\le 300000$

样例数据

输入1：

((())

输出1：

1

输入2：

)(

输出2：

2

---

题解

我来给大家讲解这道括号消除题的解题思路和代码实现~

解题思路

这道题的核心是模拟合法括号对的消除过程，但直接模拟字符串删除会超时（尤其数据量达到3e5时），所以我们用计数法高效解决：

1. 用变量z记录未匹配的左括号(数量
2. 用变量cnt记录无法匹配的右括号)数量
3. 遍历字符串：
   • 遇到左括号，直接累加未匹配左括号数
   • 遇到右括号：如果有未匹配的左括号，就配对消除（左括号数-1）；否则这个右括号无法匹配，记录下来
4. 最终剩余字符数 = 未匹配的左括号数 + 无法匹配的右括号数

这个方法时间复杂度 $O(n)$，空间复杂度 $O(1)$，完美适配大数据范围。

带注释代码（仅添加注释，不修改代码）

// 引入C++所有标准库头文件
#include <bits/stdc++.h>
using namespace std;

int main(){
    char c;           // 存储当前读取的字符
    int cnt = 0;      // 记录无法匹配的右括号 ) 的数量
    int z = 0;        // 记录未匹配的左括号 ( 的数量
    
    // 循环读取字符串中的每一个字符
    while(cin >> c){
        if (c == '('){
            z++;      // 遇到左括号，未匹配左括号数+1
        }else{
            if (z > 0){
                z--;  // 有可匹配的左括号，配对消除，左括号数-1
            }else{
                cnt++; // 无可用左括号，该右括号无法匹配，计数+1
            }
        }
    }
    
    // 最终剩余字符 = 未匹配左括号 + 无法匹配右括号
    cout << z + cnt;
    return 0;
}

代码解释

1. 变量定义：
   • c：逐个读取输入的括号字符
   • z：统计当前还没配对的左括号数量
   • cnt：统计没有左括号可以配对的右括号数量
2. 遍历逻辑：
   • 左括号：直接暂存，等待后续右括号配对
   • 右括号：优先和前面的左括号配对，无左括号可配则标记为剩余字符
3. 结果计算：配对完成后，剩下的左括号和无法配对的右括号就是最终剩余的字符。

---

总结

1. 核心思路：用计数替代字符串删除，高效处理大数据量
2. 两个变量分工：z存未匹配左括号，cnt存无法匹配右括号
3. 最终答案：z + cnt，时间复杂度线性，空间常数级