题目大意是给定一个只有左右括号组成的字符串，求最长的valid字串长度，比如“()”的最长valid字串长度为2，“)()())”的最长valid字串为”()()“，则长度为4.

拿到这个题目第一反应就是用Stack，但是Stack里面装什么呢？如何表示Valid最大长度？后来想到是否能够把还没匹配好的括号的index放到stack中，如果有匹配的就pop，没有就push。当pop的时候判断stack是否为空，如果空了，则该index之前的字串都是valid；如果不为空，则该index与stack中的peek之差就是当前valid子串的长度。 代码如下：

public class Solution {  
    public int longestValidParentheses(String s) {  
        int max = 0;  
        if (s == null || s.isEmpty()) return max;  
        int len = s.length();  
        Stack<Integer> stack = new Stack<Integer>();  
        for (int i=0; i<len; i++) {  
            char c = s.charAt(i);  
            if (c == ')' && !stack.isEmpty() && s.charAt(stack.peek()) == '(') {  
                stack.pop();  
                if (stack.isEmpty()) {  
                    max  = i+1;  
                } else {  
                    int valid_len = i - stack.peek();  
                    max = max > valid_len ? max : valid_len;  
                }  
            } else {  
                stack.push(i);  
            }  
        }  
        return max;  
    }  
}  

看到一篇博文，也可以用一维DP去解，等有空时再细研究。附上链接：点击打开链接