Solution
发现括号序列便想到栈。你一定做过下面这样的题目:
给一个长度为\(n\)的括号序列,定义:
- (),[],{}是合法的。
- 如果A是合法的,那么(A),[A],{A}也是合法的。
- 如果A,B是合法的,那么AB也是合法的。
判断这个序列合不合法,时间复杂度要求在\(\mathcal{O}(n)\)内。
这个当然是很好想了。对于每个字符串,如果是左括号,就直接进栈,如果是右括号,判断栈顶的左括号是否与之匹配,不是则不合法。最后判断栈是否为空。
考虑到原问题,我们发现,对于一端合法的子序列。如果将其单独用一个栈来维护,那最后一定是空栈。如果放到主栈中,在从加入这个子序列之前和加完之后是一模一样的(因为全部弹出了)。所以,在第\(i\)个字符时的当前最长合法序列为\(S[top + 1 \sim i]\),取最大即可。
时间复杂度\(\mathcal{O}(n)\)。
# include <bits/stdc++.h>
using namespace std;
const int N = 100002;
int k = 0;
char s[N];
int ans = 0;
stack <int> q;
int main(void)
{
scanf("%s",s + 1);
int n = strlen(s + 1);
// printf("n = %d\n",n);
for(int i = 1; i <= n; i++)
{
if(!q.empty())
{
char top = s[q.top()];
if(s[i] == ')' && top == '(' || s[i] == ']' && top == '[' || s[i] == '}' && top == '{')
{
q.pop();
}
else q.push(i);
}
else q.push(i);
if(!q.empty())
{
ans = max(ans,i - q.top());
}
else
{
ans = max(ans,i);
}
}
printf("%d\n",ans);
return 0;
}