LeetCode--最长有效括号匹配（动态规划，栈）

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

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”
示例 2:

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

动态规划

动态规划思想：将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

当前为左括号

需用到辅助数组d[s.length()]，表示从当前字符开始，到字符串结尾的最长有效括号子串长度（当前字符需为有效括号子串的第一个字符）

解题思路：从字符串结尾往前处理，求辅助数组d[]

当前字符下标为index，若当前字符为左括号’(’，判断index+1+d[index+1]位置的字符是否为右括号’)’，若为右括号，则d[index] = d[index+1]+2，并且判断index+1+d[index+1]+1位置的元素是否存在，若存在，则d[index] += d[index+1+d[index+1]+1]（解决上述两个有效括号子串直接相邻的情况）

/*
 * @Author liuhaidong 
 * @Description  当前为左括号
 * @Date 17:05 2019/9/17 0017
 **/
public int longestValidParentheses(String s) {
    if(null == s) return 0;

    int len = s.length(), max = 0;
    int[] d = new int[len];

    for(int index = len-2; index >= 0; index--){
        int symIndex = index+1+d[index+1];
        if('(' == s.charAt(index) && symIndex < len && ')' == s.charAt(symIndex)){
            d[index] = d[index+1]+2;
            if(symIndex+1 < len){
                d[index] += d[symIndex+1];
            }
        }

        max = Math.max(max, d[index]);
    }
    return max;
}

当前为右括号(待继续研究)

本题我一开始是想使用动态规划做的。opt[s.length()] 这个在当是右括号的时候记录长度。
例子: (()) 获取当前括号的长度就是前面括号的长度加上自己的长度 那么递归式就得出当前的括号长度 = 前一个括号长度 + 自己括号的长度：opt[i] = opt[i-1]+2 。
但是之前的例子： ()() 假如在当前括号之前有括号，长度也要计算进去。 其实我们很容易可以知道 当前括号的左括号的位置 = 我们当前括号的位置 - 中间括号的长度 即是 i - opt[i-1] -1 （如果再-1 就是前面括号的右括号的位置了）
那么 我们的递归式就要修改为 opt[i] = opt[i-1] + 2 + opt[i - opt[i-1] -2] 这样就可以将当前的括号长度与之前的括号长度加在一起。

public static int longestValidParentheses3(String s) {
    if(s.length()<2){
        return 0;
    }
    int[] opt = new int[s.length()];
    opt[0] = 0;
    int sum =0;
    for(int i = 1;i<s.length();i++){
        //当是右括号的时候进入判断
        if(s.charAt(i)==')'){
            //获取前面的括号的位置
            int key = i - opt[i-1] -1;
            if(key>=0){
                if(s.charAt(key)=='('){
                    if(key==0){//当是0时 说明没有前面的括号了
                        opt[i] = opt[i-1] + 2;
                    }else{//不是0时 说明当前括号的位置之前还有括号，把他们的长度加上。
                        opt[i] = opt[i-1] + 2 + opt[key-1];
                    }
                }
            }
        }
        if(sum<opt[i]){
            sum = opt[i];
        }
    }
    return sum;
}

栈

// 进栈出栈验证, 出现不匹配时清空堆栈
// 由于只有一种括号类型, 因此只需要记录在栈中的左括号的数量即可
// 对遇到的所有有效情况记录最大值
// 由于最后可能遇到一个末端无效的串
// 但前面有效部分可能是最大的,
// 因此进行一次反转后，再次计算，求最大值

/**
* @Auther: liuhaidong
* Data: 2019/9/17 0017、17:42
* Description: 用栈来解决
* @version: 1.0
*/
public class longestValidParenthesesStack {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(“请输入括号串：”);
String str = sc.nextLine();
System.out.println(longestValidParentheses(str.substring(1,str.length()-1)));
}

    public static int longestValidParentheses(String s) {
        int max = 0, count = 0;
        if(null == s) return 0;

        int len = s.length();

        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for(int index = 0; index < len; index++){
            //遇左括号(，压栈(栈中元素为当前位置所处的下标)
            if('(' == s.charAt(index)){
                stack.push(index);
            } else {
                stack.pop();
                //先弹出
                if(stack.isEmpty()){
                    stack.push(index);
                }
                //计算子串的长度
                count = index -stack.peek();
                max = max >count ? max :count;
            }
        }
        return max;
    }
}

**这种方式牛，自己没有想到，对栈里面的操作是下标，而不是字符，所以这个时候更容易记录最大值，厉害了！！！**