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;
    }
}

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