题意概括

给定一个只包含 '(' 和 ')' 两种字符的字符串，你需要找出其中最长的有效（格式正确且连续）括号子串的长度。

数据范围:

• $T$ 组测试用例, $1 \le T \le 10$
• 字符串长度 $L$ 满足 $0 \le L \le 3 \times 10^4$

基础知识

解决括号匹配相关的问题，栈 是一种非常经典且有效的数据结构。本题要求的是最长连续有效子串的长度，我们同样可以借助栈来巧妙地解决。

算法思路 (栈):

我们的核心思路是利用栈来存储还未匹配的左括号 '(' 的 索引。当遇到一个右括号 ')' 时，它就能与栈顶的左括号形成一对匹配，此时我们就可以根据索引计算出有效长度。

1. 初始化: 创建一个栈，并预先在栈底放入一个 -1。这个 -1 作为一个“哨兵”或者说“基准点”，它有两个作用：

   • 防止在弹出第一个匹配对的左括号后栈变为空，从而简化逻辑。
   • 作为计算有效长度的起始边界。例如，对于字符串 ()，当 ) 匹配掉 ( 后，长度由当前 ) 的索引 1 减去栈顶的 -1 得到 1 - (-1) = 2。

2. 遍历字符串:

   • 当遇到 '(' 时，将其在字符串中的 索引 压入栈中。
   • 当遇到 ')' 时，弹出栈顶元素。
     • 如果弹出后栈为空：这说明当前的 ')' 是多余的，它无法和任何 '(' 匹配。此时，这个 ')' 成为了一个新的“断点”。我们将这个 ')' 的索引压入栈中，作为后续计算长度的新基准点。
     • 如果弹出后栈不为空：这说明当前的 ')' 成功匹配了一个 '('。此时，栈顶的元素就是当前有效子串前一个无法匹配的字符的索引。因此，当前有效子串的长度就是当前 ')' 的索引减去新的栈顶元素的索引。我们用这个长度来更新全局的最大长度。

该算法对字符串进行单次遍历，每个索引最多入栈出栈一次，因此时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void slv() {
    string s;
    cin >> s;

    stack<int> stk;
    stk.push(-1); // 放入哨兵索引
    int ans = 0;

    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '(') {
            stk.push(i);
        } else {
            stk.pop();
            
            if (stk.empty()) {
                // 当前 ')' 没有匹配的 '('，成为新的断点
                stk.push(i);
            } else {
                // 计算并更新最大长度
                ans = max(ans, i - stk.top());
            }
        }
    }

    cout << ans << endl;
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        slv();
    }

    return 0;
}

/*
样例输入 1:
4
(()
)()())
""
()(()

样例输出 1:
2
4
0
2

样例输入 2:
3
()()
(())()
)(

样例输出 2:
4
6
0
*/