32 Longest Valid Parentheses

Leetcode

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

---

动态规划解法。dp 存放当前位置为结尾的最长有效括号对数。遍历字符串，countLeft 计算左括号数量，如果遇到有括号，前面有左括号，此时有效括号对数相当于上一个位置加 1 。求解当前位置结尾的有效括号的前一个位置，加上前面一段有效括号的长度。

时间复杂度 o(n) ，空间复杂度 o(n)

public int longestValidParentheses(String s) {
    int len=s.length();
    int index=0;
    int[] dp=new int[len];
    int countLeft=0;
    int max=0;
    for(int i=0;i<len;++i){
        char c=s.charAt(i);
        if(c=='('){
            countLeft++;
        } else {
            if(countLeft>0){
                countLeft--;
                int pairs=1+dp[i-1];
                int preIndex=i-2*pairs;
                if(preIndex>=0) pairs+=dp[preIndex];
                dp[i]=pairs;
                if(pairs>max) max=dp[i];
            }
        }
    }
    return max*2;
}

从左向右遍历有效括号时，任意时刻左括号数量是大与等于有括号数量的，且结尾处左右括号数量相等，反之，从右向左遍历人意时刻有括号数量大于等于左括号数量。遍历字符串，如果违反左右括号数量，则重新计数，遇到左右括号数量相等时，计算长度。只遍历一次无法保证找到最长合法括号子字符串。子字符串把字符串分为两部分，左半部分和右半部分。左半部分如果左括号多，会导致遍历完合法字符串时左右括号数量不相等，但此时右半部分一定也是左括号多，从右边遍历就是可行的，反之亦然。

时间复杂度 o(n) ，空间复杂度 o(1)

public int longestValidParentheses(String s) {
    int left=0, right=0;
    int max=0;
    for(int i=0;i<s.length();++i){
        if(s.charAt(i)=='(') left++;
        else right++;
        if(left==right){
            if(left>max) max=left;
        } else if(left<right){
            left=0;
            right=0;
        }
    }
    left=0;
    right=0;
    for(int i=s.length()-1;i>=0;--i){
        if(s.charAt(i)=='(') left++;
        else right++;
        if(left==right){
            if(left>max) max=left;
        } else if(left>right){
            left=0;
            right=0;
        }
    }
    return max<<1;
}

使用一个栈，存放合法括号子字符串的左边的下标。遍历字符串，判断当前位置是否可以成为合法括号的结尾，如果可以，弹出一个左括号下标，根据栈顶计算长度。否则，将当前位置压入栈。

时间复杂度 o(n) ，空间复杂度 o(n)

public int longestValidParentheses(String s) {
    int max=0;
    Deque<Integer> stack=new LinkedList<>();
    stack.push(-1);
    for(int i=0;i<s.length();++i){
        if(s.charAt(i)==')' && stack.size()>1 && s.charAt(stack.peek())=='('){
            stack.pop();
            int len=i-stack.peek();
            if(len>max) max=len;
        } else {
            stack.push(i);
        }
    }
    return max;
}