AcWing 150. 括号画家
原题链接
简单
作者:
wjie
,
2020-07-29 19:47:03
,
所有人可见
,
阅读 640
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
stack<int> sta;
char str[N];
int res;
int main()
{
sta.push(0);
scanf("%s", str+1);
for (int i = 1; str[i]; ++i)
{
res = max(res, i-sta.top()-1);
if (str[i] == ')' && sta.size() && str[sta.top()] == '(') sta.pop();
else if(str[i] == ']' && sta.size() && str[sta.top()] == '[') sta.pop();
else if (str[i] == '}' && sta.size() && str[sta.top()] == '{') sta.pop();
else sta.push(i);
// cout << str[i] << " " << res << endl;
}
int temp = strlen(str+1)-sta.top();
res = max(res, temp);
printf("%d", res);
return 0;
}
push(0)之后不加s.size()也是对的啊
为什么push(0)呢,
res = max(res, i-sta.top()-1)
这里i-sta.top()-1 求的是 下标为[sta.top()+1, i-1]之间被删除的长度,(也就是一段连续的美观括号的长度)
一开始push(0)是防止边界情况,可能这个连续的美观括号的长度是从1, i-1的,这样sta就为空了,所以用0作为边界.
谢谢大佬