算法：leetcode 32 最长有效括号

题意

输入类似“（（（））（"，请找出最长的有效括号。

分析

对于任意的一个有效括号来说，它肯定是一个”（“一个左括号开始的，然后以一个”）“右括号结束，中间可以包含其他的有效括号或者没有。
这和之前我们判断是否是合法括号的方式是一样的* 用之前思考有效括号的方案，我们使用栈来做 对输入的每一个字符下标为i都进行入栈操作，一旦碰到“）”我们应该出栈进行匹配，如果能匹配这时候的长度及应该是 i - 栈顶的元素的下标，这里可能会难以理解为什么是栈顶的下标？ 比如：（）()。比如出现这种类似的结构，每次我们遇到“）”进行出栈的时候，栈内都是空的，栈内都是空代表了从0——i这所有的括号都被匹配过了！不是吗?不然我的栈为什么为空，为空就代表了之前入栈的所有元素都是被匹配过了！ 这时候我们的长度应该是 i - 0 +1。 如果我们出栈的时候不会空，当前栈顶栈顶的元素下标为K，很明显K+1 —— i的元素都被匹配了 这时候我们的长度应该是 i -（k+1）+1 = i -k.
想通了思路代码就很好实现了

   public int longestValidParentheses(String s) {
        if ( s == null ||s.length() == 0 || s.length() == 1)
            return 0;
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '('){
                stack.push(i);
            }else {
                if (!stack.isEmpty()){
                    int index  = stack.peek();
                    if (s.charAt(index) == '(' ){
                        //配对成功
                        stack.pop();
                        max =Math.max(stack.isEmpty()?i+1:i - stack.peek(),max);
                    }else {
                        stack.push(i);
                    }
                }else {
                    stack.push(i);
                }
            }
        }
        return max;
    }

每次都去判断栈为空有点繁琐，我们还可以对起进行优化，我们定义-1入栈，这样栈永远都不会为空。

 public int longestValidParentheses (String s){

        if ( s == null ||s.length() == 0 || s.length() == 1)
            return 0;
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '('){
                stack.push(i);
            } else {
                int index = stack.peek();
                if (index > -1 && s.charAt(index) == '(') {
                    //配对成功
                    stack.pop();
                    max = Math.max(i - stack.peek(), max);
                } else {
                    stack.push(i);
                }
            }
        }
        return max;
    }

想通了思路，还可以通过左右扫描来做，也可以通过动态规划。