Given a string containing just the characters ‘(‘ and ‘)‘, find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
可以用 DP或者Stack来解。
栈 Stack：定义个start变量来记录合法括号串的起始位置，遍历字符串，如果遇到左括号，则将当前下标压入栈，如果遇到右括号，如果当前栈为空，则将下一个坐标位置记录到start，如果栈不为空，则将栈顶元素取出，此时若栈为空，则更新结果和i - start + 1中的较大值，否则更新结果和i - 栈顶元素中的较大值。
Java:
public static int longestValidParentheses(String s) {
Stack<int[]> stack = new Stack<int[]>();
int result = 0;
for(int i=0; i<=s.length()-1; i++){
char c = s.charAt(i);
if(c==‘(‘){
int[] a = {i,0};
stack.push(a);
}else{
if(stack.empty()||stack.peek()[1]==1){
int[] a = {i,1};
stack.push(a);
}else{
stack.pop();
int currentLen=0;
if(stack.empty()){
currentLen = i+1;
}else{
currentLen = i-stack.peek()[0];
}
result = Math.max(result, currentLen);
}
}
}
return result;
}