【ACWing】150. 括号画家

题目地址：

https://www.acwing.com/problem/content/152/

达达是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。这一天，刚刚起床的达达画了一排括号序列，其中包含小括号 ( )、中括号 [ ] 和大括号 { }，总长度为N NN。
这排随意绘制的括号序列显得杂乱无章，于是达达定义了什么样的括号序列是美观的：

1. 空的括号序列是美观的；
2. 若括号序列 A是美观的，则括号序列 (A)、[A]、{A}也是美观的；
3. 若括号序列 A、B都是美观的，则括号序列AB也是美观的。例如[(){}]()是美观的括号序列，而)({)[}](则不是。

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

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

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

数据范围：
字符串长度不超过1 0 5 10^5105。

可以用栈来做。当栈空，或者栈顶与遍历到的字符不匹配的时候，将下标入栈。这样栈顶存的就是最长美观子串的起始位置。如果匹配，则pop栈顶，并更新答案。代码如下：

#include<iostream>#include<stack>usingnamespacestd;intn;string s;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>s;n=s.size();s=" "+s;automatch=[](chara,charb){returna=='('&&b==')'||a=='['&&b==']'||a=='{'&&b=='}';};stack<int>stk;intres=0;for(inti=1;i<=n;i++){charch=s[i];if(ch=='('||ch=='['||ch=='{')stk.push(i);else{if(stk.empty()||!match(s[stk.top()],ch))stk.push(i);else{stk.pop();res=max(res,i-(stk.size()?stk.top():0));}}}printf("%d\n",res);}

时空复杂度O ( N ) O(N)O(N)。