🎯 兔猫括号大作战

（Rabbit‑Cat Informatics Academy · 加菲老师实战）

故事背景

午后的算法自习课，小兔和小猫正在练习键盘手速。加菲老师忽然举起一张写满 '(' 与 ')' 的长纸条：“同学们，谁能一眼看出这张纸里最长的一段合法括号有多长？”

“合法”意味着括号要 连续、匹配正确，就像一段完美的伸缩臂——伸出去的每一个 '(' 都能被相应的 ')' 收回来。 小兔眨巴着眼：“要是删掉或打乱顺序可不行哦！” “正解！”加菲老师拍拍双爪，“请写程序，在一串括号里找出最长合法子串的长度。” 挑战开始……

---

题目描述

给定只包含字符 '(' 与 ')' 的字符串 $s$，求其中 最长的连续且括号匹配正确 的子串长度。若不存在有效括号子串，输出 $0$。

---

输入格式

n
s

• $n$ — 字符串长度
• $s$ — 仅由 '(', ')' 组成的长度为 $n$ 的字符串

输出格式

ans

• ans — 最长有效括号子串的长度

---

3
(())

2

样例解释 1

最长合法子串为 "()"，长度为 $2$。

---

6
)()())

4

样例解释 2

最长合法子串为 "( ) ( )"（索引 $1!\sim!4$），长度 $4$。

---

数据范围

参数	取值
$0 \le n \le 3\times10^{4}$

---

✨ 解题思路

常用三种 $O(n)$ 解法，这里给出 栈 + 辅助下标 的写法：

1. 维护栈 st，初始存哨兵 -1。

2. 遍历下标 $i$：

   • 若 s[i]=='(' ⇒ push(i)。
   • 否则弹栈；若栈为空则 push(i)（新的哨兵）。
   • 每次成功匹配后，用 i - st.top() 更新答案。

哨兵保证随时能取到合法起点。