题目描述

leetcode32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

 

示例 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
36
class 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;
    }
};