宁愿相信世上有鬼，也不能随便相信某谷题目标签
我想了半天然后看了眼题解，发现用栈来模拟就好了
栈来模拟，还要用到一个bool数组，标记是否已经匹配 use[ i ]
一串括号，入栈，遇到匹配的就弹出去，标记已经匹配，然后最后挑连续匹配的最大的就好了，因为题目要求子串
1.q[top]数组存的是括号的标号，而不是top是存的括号标号
2.res记录暂时一共有多少个连续的匹配括号数，所以每遇到一个新的括号，都要更新一遍
具体可以结合代码
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<string> #include<cstring> #include<queue> using namespace std; typedef long long ll; inline int read() { int ans=0; char last=‘ ‘,ch=getchar(); while(ch<‘0‘||ch>‘9‘) last=ch,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) ans=ans*10+ch-‘0‘,ch=getchar(); if(last==‘-‘) ans=-ans; return ans; } const int maxn=1e6+10; char s[maxn]; bool use[maxn]; int top=0,q[maxn]; int l,r,ans=0,res=0,l1=0,r1=0; int main() { scanf("%s",s+1); int len=strlen(s+1); memset(use,0,sizeof(use)); for(int i=1;i<=len;i++){ if((s[q[top]]==‘(‘&&s[i]==‘)‘)||(s[q[top]]==‘[‘&&s[i]==‘]‘)){ use[q[top--]]=1; use[i]=1; } else{ q[++top]=i; } } for(int i=1;i<=len;i++){ if(!use[i]){ if(res>ans) ans=res,l=l1,r=r1; res=0; //不可以放到if里面 } else{ if(res==0) l1=r1=i; else r1++; res++; //不可以放到if里面 } } if(res>ans) ans=res,res=0,l=l1,r=r1; for(int i=l;i<=r;i++) printf("%c",s[i]); return 0; }
1.())[]())[]
2.())[]([(][()]]()
原文：https://www.cnblogs.com/xiaoyezi-wink/p/11922409.html