leetcode 32. 最长有效括号
题目描述
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
输入:s = "(()" 输出:2 解释:最长有效括号子串是 "()"
示例 2:
输入:s = ")()())" 输出:4 解释:最长有效括号子串是 "()()"
示例 3:
输入:s = "" 输出:0
提示:
0 <= s.length <= 3 * 104
s[i]
为'('
或')'
题解——计数法(滑动窗口)
思路
想要求一个满足条件的最长连续子串,很自然地想到使用滑动窗口
我们需要知道的是左边界滑动的条件
所以要考虑,如果不能形成有效括号,是怎样的情况
应当说,要么是有多余的左括号,要么是有多余的右括号(好像是废话😂,但其实这就是本质)
考虑"())"
这个字符串,扫描到第二个)
时,就知道不可能有基于前面的合法的括号了,因为这个右括号是永远匹配不上的,此时,应当移动左边界到下一个位置继续搜索。
然而,在这样一次遍历中,我们并不知道什么时候会有多余的左括号,因为我们无法预知后面会不会有右括号与之匹配
因此,我们直到最后才能发现左括号多了,但在这一段子串里却可能隐藏着答案
不过,可以断言,在这一次搜索中,所有不是由于左括号多余而不匹配的子串都被查找过了
那么,如果将该过程反过来进行一次,可以得到对称的结论,即所有不是因为右括号多余而不匹配的子串都被查找过了
二者相并,我们就查找过了所有合法子串,得到了正确的答案。
代码实现
用left和right计数,正向遍历时,遇到左括号++left
,遇到右括号考虑是否多余,如果是,则重置,如果不是,++right
,如果left和right相等,说明是合法子串,比较ans和2*left
然后再反向搜索一遍即可1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class Solution {
public:
int longestValidParentheses(string s) {
int left=0,right=0,ans=0;
for(int i=0;i<s.size();++i)
{
if(s[i]=='(')
++left;
else
{
if(left==right)//这是多余的右括号
left=right=0;
else
++right;
}
if(left==right&&2*left>ans)
ans=2*left;
}
left=right=0;
for(int i=s.size()-1;i>=0;--i)
{
if(s[i]==')')
++right;
else
{
if(left==right)//这是多余的左括号
left=right=0;
else
++left;
}
if(left==right&&2*left>ans)
ans=2*left;
}
return ans;
}
};