51nod 1791 合法括号子段(单调栈)

有一个括号序列,现在要计算一下它有多少非空子段是合法括号序列。

合法括号序列的定义是:

1.空序列是合法括号序列。

2.如果S是合法括号序列,那么(S)是合法括号序列。
3.如果A和B都是合法括号序列,那么AB是合法括号序列。

Input

Output

Input示例

Output示例

一开始写了个错误的O(nlogn)的做法,然后一直打补丁也过不去。。。然后请教了一下fls,发现O(n)做法简直比O(nlogn)好写。

考虑把左括号加1,右括号加负一。那么这个序列的前缀和一定是山峰状的,那么合法的子段的最右边一定是右括号,也就是在山峰的下降处,那么我们用一个单调栈维护这个高度,对于插入一个高度,我们把比他高的都弹出,然后计算这个高度相同的值有多少个即可。注意假如前缀和为负,需要整个栈清空。。。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注