题目描述

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

样例

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

算法1

(基于栈的实现) $O(n)$

用栈（或者双端队列）记录未匹配成功的括号的下标。因为合法括号均成对出现，所以，对于“(”我们直接压栈，当遇到“)”时，比较栈顶角标对应的元素，如果是“(”，直接弹出，如果不是，将当前角标压栈（相当于更新可以匹配括号的左侧角标）。

Java 代码

class Solution {
    public int longestValidParentheses(String s) {
        LinkedList<Integer> queue=new LinkedList<>();
        int res=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                queue.addLast(i);
            }else{
                if(!queue.isEmpty()&&s.charAt(queue.peekLast())=='('){
                    queue.pollLast();
                    if(queue.isEmpty()){
                        res=Math.max(res,i+1);
                    }else{
                        res=Math.max(res,i-queue.peekLast());
                    }
                }else{
                    //添加左边界下标
                    queue.addLast(i);
                }
            }
        }
        return res;
    }
}

算法2

(动态规划实现) $O(n)$

状态表示：
集合：f[i]表示以s[i]为结尾的合法括号的集合；
属性：最大值

状态计算：
合法括号只考虑“)”所在的位置即可，由于是求最大值，所以初始值为0。当s[i]==’)’时，s[i-1]可能存在几种情况：
1.s[i-1]==’(‘，此时f[i]=f[i-2]+2 ;主要此时i必须大于等于2；
2.s[i-1]==’)’，此时就需要考虑上一个’(‘的位置，如果s[i-1]位置是合法的括号，考虑到f[i]的定义，我们可以确定s[i]上一个’(‘的位置为 i-f[i-1]-1 ,只需要判断s[i-f[i-1]-1]是否为’)’即可，注意情况1中的判断，不要遗漏f[i-f[i-1]-2]这一项！

Java 代码

class Solution {
    public int longestValidParentheses(String s) {
        int res=0;
        int[] f=new int[s.length()+1];
        for(int i=1;i<s.length();i++){
            if(s.charAt(i)==')'){
                if(s.charAt(i-1)=='('){
                    f[i]=2;
                    if(i>=2){
                        f[i]+=f[i-2];
                    }
                }else{
                    if(i-f[i-1]>0&&s.charAt(i-f[i-1]-1)=='('){
                        f[i]=f[i-1]+2;
                        if(i-f[i-1]>=2){
                            f[i]+=f[i-f[i-1]-2];
                        }
                    }
                }
            }
            res=Math.max(res,f[i]);
        }
        return res;
    }
}