advancing5

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/longest-valid-parentheses/]

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

1
2
3
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

1
2
3
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

算法描述

正向遍历一次数组，碰到'('的话，left++,如果碰到)的话，right++，当right==left时更新最长括号的长度，再反向遍历一遍重复遍历一遍，要注意的是，正向遍历时right>=left时清零right和left,反向时left>=right时清零，直到遍历完两次数组；

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.length()<=1)return 0;
        int l = 0,r = 0;
        int maxLen=0;
        for(int i=0;i<s.length();i++){
            if(s[i]=='(')l++;
            else r++;
            if(l==r)maxLen = max(maxLen,2*r);
            else if(r>l)l=r=0;
        }
        l=r=0;
        for(int i=s.length()-1;i>=0;i--){
            if(s[i]=='(')l++;
            else r++;
            if(l==r) maxLen = max(maxLen,2*l);
            else if(l>r)l=r=0;
        }
        return maxLen;
    }
};

Java代码

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) {
        if(s.length()<=1)return 0;
        int left=0;
        int right=0;
        int maxLen=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                left++;
            }else if (s.charAt(i)==')'){
                right++;
            }
            if(left==right){
                maxLen = Math.max(maxLen,right*2);
            }else if(right>=left){
                left = right = 0;
            }
        }
        
        left = right = 0;
        
        for(int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)=='('){
                left++;
            }else if (s.charAt(i)==')'){
                right++;
            }
            if(left==right){
                maxLen = Math.max(maxLen,right*2);
            }else if(right<=left){
                left = right = 0;
            }
        }
        return maxLen;
    }
}