32. 最长有效括号 java解决

题目描述：

难度：困难
相关标签：栈、字符串、动态规划

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

示例 1：
    输入：s = "(()"
    输出：2
    解释：最长有效括号子串是 "()"
示例 2：
    输入：s = ")()())"
    输出：4
    解释：最长有效括号子串是 "()()"
示例 3：
    输入：s = ""
    输出：0

提示：
    0 <= s.length <= 3 * 104
    s[i] 为 '(' 或 ')'

方法一（官方答案）：动态规划

思路和算法：

 代码：

class Solution {
    public int longestValidParentheses(String s) {
 
        //官方答案
        int maxans = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}

方法二（自己的方法）：栈

class Solution {
    public int longestValidParentheses(String s) {
        
        //我自己的答案，打败5%的对手
        int[] flag = new int[ s.length() ];   //0：表示没匹对的， 1：表示又匹对的， 2-表示（ ， 3-表示）
 
        int n = 0;
        int longest = 0;   //记录最长括号对
        Stack<Integer> stack = new Stack<>();
        for ( int i = 0; i < s.length(); i++ ) {
            char c = s.charAt( i );
            if( c == '(' ) {
                stack.push( i );
                flag[ i ] = 2;
                n ++;
            }
            else if( c == ')' ) {
                flag[ i ] = 3;
                if ( stack.size() > 0 ) {
                    flag[ i ] = 1;
                    int j = stack.pop();
                    flag[ j ] = 1;
                }
            }
        }
        String t = "";
        for ( int i : flag )
            t += i;
        System.out.println( t );
        String[] str = t.split("2|3" );
        for ( int i = 0; i < str.length; i++ ) {
            if ( ! str[ i ].contains( "3" ) ) {
                longest = Math.max( longest, str[ i ].length() );
            }
        }
 
        return longest;
}

官方的栈的方法（用Deque打败54%对手，用stack打败20+%的对手）：

class Solution {
    public int longestValidParentheses(String s) {
        
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        // Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}