题目描述
达达是一名漫画家,她有一个奇特的爱好,就是在纸上画括号。
这一天,刚刚起床的达达画了一排括号序列,其中包含小括号( )、中括号[ ]和大括号{ },总长度为N。
这排随意绘制的括号序列显得杂乱无章,于是达达定义了什么样的括号序列是美观的:
(1) 空的括号序列是美观的;
(2) 若括号序列A是美观的,则括号序列 (A)、[A]、{A} 也是美观的;
(3) 若括号序列A、B都是美观的,则括号序列AB也是美观的。
例如 [(){}]()
是美观的括号序列,而)({)[}](
则不是。
现在达达想在她绘制的括号序列中,找出其中连续的一段,满足这段子序列是美观的,并且长度尽量大。
你能帮帮她吗?
样例
输入样例:
({({(({()}})}{())})})[){{{([)()((()]]}])[{)]}{[}{)
输出样例:
4
算法1
(贪心+栈) $O(n)$
首先证明如果a, b是合法的括号序列,c, d是合法的括号序列,那么a, d也是合法的括号序列。
证明:
假设’(‘ 记为+1, ‘)’记为 -1, 那么有$x + y = 0, y + z = 0$, 可以得出$x = z$。
并且由于$x >= 0, y >= 0$ 所以$x = 0, y = 0$。
最后由于第一步得出$x = z$, 所以$z = 0$。
因此两段合并也是合法括号序列。
按照以上方法取求极大括号序列,可能存在不同起点,极大值不同,因此我们可能需要枚举不同的起点,然后再求极大值。就不一定从最靠左的位置开始往栈里push括号。
有了这个性质以后,求极大的括号序列,就只需要从起点开始枚举。 。(也就是视频中29:00
说的只有一种决策)
代码中需要注意的点:
stk
记录的下标值,方便计算最大长度。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <stack>
using namespace std;
int main(){
string str;
stack<int> stk;
cin >> str;
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;
}