题意
输入类似“（（（））（"，请找出最长的有效括号。
分析
对于任意的一个有效括号来说，它肯定是一个”（“一个左括号开始的，然后以一个”）“右括号结束，中间可以包含其他的有效括号或者没有。
这和之前我们判断是否是合法括号的方式是一样的* 用之前思考有效括号的方案，我们使用栈来做 对输入的每一个字符下标为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;
}
想通了思路，还可以通过左右扫描来做，也可以通过动态规划。
