题目描述

达达是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。

这一天，刚刚起床的达达画了一排括号序列，其中包含小括号( )、中括号[ ]和大括号{ }，总长度为N。

这排随意绘制的括号序列显得杂乱无章，于是达达定义了什么样的括号序列是美观的：

(1) 空的括号序列是美观的；

(2) 若括号序列A是美观的，则括号序列 (A)、[A]、{A} 也是美观的；

(3) 若括号序列A、B都是美观的，则括号序列AB也是美观的。

例如 (){} 是美观的括号序列，而)({)[}]( 则不是。

现在达达想在她绘制的括号序列中，找出其中连续的一段，满足这段子序列是美观的，并且长度尽量大。

你能帮帮她吗？
输入格式

输入一行由括号组成的字符串。
输出格式

输出一个整数，表示最长的美观的子段的长度。
数据范围

字符串长度不超过100000。

样例

输入
({({(({()}})}{())})})[){{{([)()((()]]}])[{)]}{[}{)
输出
4

题解

这道题目题意就是，求出一段最长的连续的匹配的括号

每次读入一个字符，并记录这个字符的坐标，从1开始；
对于每个字符分两种情况讨论

1.栈不为空，且当前字符和栈顶字符匹配
对于这种情况：
①移出栈顶字符
②求出当前字符的位置和删除之后的栈顶字符位置之间的距离，并更新答案
注意讨论栈是否为空！！！
此时的栈顶字符必定没有发生匹配，且栈顶字符之后的位置都发生了匹配；
设栈顶坐标为j，当前字符坐标为i，那么更新的答案就是max（ans，i-j）
如果栈为空，这时候相当于j=0，那么答案就是max（ans，i）

2.对于其他情况，不可能发生匹配
那么直接将这个字符放入栈中即可

时间复杂度 $O(n)$

C++ 代码

/*超简洁代码*/
#include <bits/stdc++.h>
using namespace std;
int  main()
{
    int n=0;
    int ans=0;
    char c;
    stack<pair<char,int> >s;//第一维存字符，第二维存坐标
    while(c=getchar(),n++,~c)
    {
        if(s.size()&&(c==')'&&s.top().first=='('||c==']'&&s.top().first=='['||c=='}'&&s.top().first=='{'))
        {
            s.pop();
            if(s.size())
                ans=max(ans,n-s.top().second);
            else
                ans=max(ans,n);
        }
        else
            s.push(make_pair(c,n));
    }
    cout<<ans<<endl;
    return 0;
}