题目描述

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

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

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

  1. 空的括号序列是美观的；
  2. 若括号序列 AA 是美观的，则括号序列 (A)(A)、[A][A]、{A}{A} 也是美观的；
  3. 若括号序列 A、BA、B 都是美观的，则括号序列 ABAB 也是美观的。

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

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

你能帮帮她吗？

输入格式

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

输出格式

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

数据范围

字符串长度不超过 105105。

输入样例：

({({(({()}})}{())})})[){{{([)()((()]]}])[{)]}{[}{)

输出样例：

4

思路

合法括号序列的充要条件

  1. 所有前缀中左括号的数量 >= 右括号的数量 （cnt>=0)
  2. 左括号数量 == 右括号数量（cnt == 0）

使用一个栈，从左向右扫描整个字符串

  • 遇到左括号，则入栈
  • 遇到右括号，看一下栈顶是不是对应的左括号，是的话就出栈，不是就入栈
  • 每次处理完一个字符后，就计算一下合法序列的长度，更新一下最大结果res

为什么是对的？

  1. 在扫描的过程中，所有合法的括号序列一定会被删除掉（匹配出栈），所以全部删除完之后当前元素索引值与栈顶元素索引值之差就是对应的最长的合法序列。
  2. 为什么从起始位置开始遍历是对的？回答这个问题我们要证明一个结论，所有的最长的合法序列一定是不重叠的（下面给出证明过程）。既然不重叠，那么我们就可以从起始位置遍历了。

alt

其实还有另外一种理解方式，从图形的角度理解左括号和右括号，我们的思路其实就是对每一个右括号，看看向左最长能够走到哪里，找到和它匹配的，最后取一下max

alt

代码

#include<iostream>
#include<stack>
#include<cstring>

using namespace std;

int main()
{
    string str;
    cin >> str;
    //用栈存储下标，可以方便获取当前元素和栈顶元素之间的下标之差
    stack<int> stk;

    int res = 0;
    for(int i = 0; i < str.size(); i++)
    {
        char c = str[i];
        if(stk.size())
        {
            char t = str[stk.top()];
            if(c == ')' && t == '(' || c == ']' && t == '[' || c == '}' && t == '{')
                stk.pop();
            else stk.push(i);
        }
        else
        {
            stk.push(i);
        }

        if(stk.size()) res = max(res, i - stk.top());
        else res = max(res, i + 1);
    }

    cout << res << endl;
    return 0;
}