最长有效括号

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

示例

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

解题

方法一：栈

通过栈，可以在遍历给定字符串的过程中去判断到目前为止扫描的子串的有效性，同时能得到最长有效括号的长度。
始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标。
需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为-1的元素。

1.初始化最大长度，初始化栈，-1入栈。
2.遍历：
1.遇到左括号：下标入栈
2.遇到右括号：出栈（弹出栈顶元素）
如果栈为空，当前右括号下标入栈 「最后一个没有被匹配的右括号的下标」
如果栈不为空，更新 maxlen = 当前右括号的下标减去栈顶元素。「以该右括号为结尾的最长有效括号的长度」
3.返回最长有效括号长度

class Solution {
    //最长有效括号 - 子串及其长度
    //栈底 维护最后一个没有被匹配的右括号的下标
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        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;
    }
}

//版本二：记录下标，同时输出子串
class Solution {
    //保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」
    public int longestValidParentheses(String s) {
        int maxlen = 0;
        int left = 0,right = 0;
        String sub;
        Deque<Integer> stack = new LinkedList<>();
        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{
                    if(i - stack.peek() > maxlen){
                        maxlen = Math.max(maxlen, i - stack.peek());
                        left = stack.peek();
                        right = i;
                    }
                }
            }
        }
        if(right != 0){ //空字符串处理
            sub = s.substring(left+1,right+1);
            System.out.println(left+1);  //最长子串的左下标
            System.out.println(right);   //最长子串的右下标
            System.out.println(sub);     //最长有效子串
        }
        return maxlen;
    }
}

方法二：动态规划