最长括号子串

1.动态规划

1. 对于取到第i位为左括号"("时,dp[i]设置为0,因为取到左括号时这一段的序列一定不是合法的因为多出了一个左括号

2. 对于第i为右括号")"时,有两种情况:

   a) 第 i - 1位为左括号"("时，dp[i]可以直接设置成2因为当前括号这一小段为合法,并且判断i - 2处是否有值如果有说明这是一段连续的合法序列即加上i - 2处的dp值

   b) 第i - 1为不为左括号时,说明 i - 1处是合法序列,那么我们需要找到该序列更前面的一个单一左括号, 因为合法序列之间一定存在多出的符号,那么我们只需要找到i - 1位合法序列前不合法序列的倒数第一个符号是否为左括号即可,如果是则将当前值加上2 + dp[i - 1],之后再判一下第i - dp[i - 1] - 2位是否属于一个合法序列,如果是则加上

//100%通过率
public int longestValidParentheses (String s){
        int[] dp = new int[s.length()];
        int ans = 0;
        for (int i = 1; i < s.length(); i++) {
            if(s.charAt(i)==')'){
                if(i-dp[i-1]-1>=0&&s.charAt(i-dp[i-1]-1)=='('){
                    dp[i] +=dp[i-1]+2;//前一位
                    if(i-dp[i-1]-2>=0){
                    dp[i] += dp[i-dp[i-1]-2];//前i-2位
                    }
                }
                
            }
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
    

2.栈

//70%
public int longestValidParentheses (String s){
        Stack<Character> stack = new Stack<>();
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)=='('){
                stack.push(s.charAt(i));
                count++;
            }else if(s.charAt(i)==')'&&!stack.isEmpty()){
                stack.pop();
                count++;
            }
        }
        return count-stack.size();
    }

//100%
public int longestValidParentheses (String s){
        Stack<Integer> stack = new Stack<>();
        int last = -1, max = 0;
    //如果是左括号，压栈
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)=='('){
                stack.push(i);
            }else {
                //如果是右括号，且栈为空，则不合法序列的最后一个值为i
                if(stack.isEmpty()){
                    last = i;
                }else {
                    //如果是右括号，栈不为空，则弹出一个左括号。之后再做判断，若弹出左括号后栈为空，则合法序列的长为（当前i-目前记录的最后一个不合法值的位置）与max比较大小。如果弹出后栈不为空，则比较最大值与当前弹出后i-栈顶位置的长度与max的大小。
                    stack.pop();
                    if(stack.isEmpty()){
                        max = Math.max(max,i-last);
                    }else {
                        max = Math.max(max,i-stack.peek());
                    }
                }
            }
        }
        return max;
    }