AcWing 150. 括号画家
原题链接
简单
作者:
LBG
,
2021-01-22 17:31:15
,
所有人可见
,
阅读 356
C++ 代码
/**
*https://www.acwing.com/problem/content/129/
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5+10;
const int INF = 1e8;
vector<pii>points;
vector<int>number;
char st[maxn];
bool match(char a,char b) {
if(a == '(' && b == ')') return true;
if(a == '{' && b == '}') return true;
if(a == '[' && b == ']') return true;
return false;
}
int main()
{
string s;
cin>>s;
stack<int>st;
int len = 0,ans = 0;
for(int i=0;i<s.size();i++) {
if(!st.size()||!match(s[st.top()],s[i])) {//如果栈中无元素或栈顶元素与新加入元素不匹配,入栈
st.push(i);
} else {//否则匹配,弹出栈顶
st.pop();
}
if(st.size()) {//如果匹配下来栈不为空则与本次弹出个数取一次max
ans = max(ans,i-st.top());
} else {//若匹配下来栈空则与栈中全部元素个数加上新加入的元素取一次max
ans = max(ans,i+1);
}
}
cout<<ans<<endl;
}