算法学习：leetcode32. 最长有效括号

题目

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

示例 :

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

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

思路一：暴力计算

合法括号是成对出现的,所以就判断[字符串长度/2个字符]是否是合法括号，如果是，那么就是最大长度了，举例：加入一个字符串长度是12，那么最大的合法括号就是6对，按照题目计算6*2=12，最大长度是12，我们的思路就是先从最大长度来判断，是否存在这样的可能，存在那题目直接就找到正确答案了，如果12的长度没找到，在找长度为10的，依次8，6，4，2，如果2也没找到，那就连一对合法括号都没有，return 0。

/**
     * 暴力解法
     * 合法括号是成对出现的,所以就判断 字符串长度/2个字符是否是合法括号
     * 是就是最大长度了
     * @param s
     * @return
     */
    public static int longestValidParentheses(String s) {
        int result = 0;
        Character le = new Character('(');
        Character ri = new Character(')');

        int m =s.length()%2;
        int n = s.length()-m;
        for(; n>=2; n=n-2) {
            for(int i=0; i+n<=s.length(); i++) {
                Stack<Character> stack = new Stack<>();
                for(int j=i; j<i+n; j++) {
                    if(le.equals(s.charAt(j))) {
                        stack.push(s.charAt(j));
                    }
                    if(ri.equals(s.charAt(j))) {
                        if(stack.empty()) {
                            result = -1;
                            break;
                        }
                        Character peek = stack.peek();
                        if(!le.equals(peek)) {
                            continue;
                        } else {
                            stack.pop();
                        }
                    }
                }

                if(stack.isEmpty()) {
                    if(result <0) {
                        result = 0;
                        continue;
                    }
                    return n;
                }
            }
        }
        return 0;
    }

按照上面的思路和代码，是没有问题的，但是这样解效率太低，leetcode还是不通过，因为超时，所以我们就要换一个思路，这个思路也比较容易理解。

思路二就是用stack来解题

/**
     * 识别成对括号
     * 检查stack是否为空
     * 检查中间括号是否把合法括号分割开,计数要重新开始
     * @param s
     * @return
     */
    public static int longestValidParentheses(String s) {
        int max_len = 0;
        Character le = new Character('(');
        Character ri = new Character(')');
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for(int i=0; i<s.length(); i++) {
            if(le.equals(s.charAt(i))) {
                stack.push(i);
                continue;
            }
            stack.pop();
            if(ri.equals(s.charAt(i))) {
                if(stack.isEmpty()) {
                    stack.push(i);
                    continue;
                }
                max_len = Math.max(i-stack.peek(), max_len);
            }
        }
        return max_len;
    }

这里有一些巧妙的地方，其一就是先往stack中放一个-1，其二就是当stack出栈变为空了之后，就将一个右括号的下标入栈，为什么这样做呢，其实就是为了计算连续有效括号的长度。细品一下。

还有一种思路是采用动态规划，这里主要以思路简单易于理解，易于入门为主，dp就先不在这里讲解了。