image.png
这道题一开始还是有点思路的，可以用堆栈的方法来写：
class Solution {
public int longestValidParentheses(String s) {
if(s.length()==0) return 0;
Stack<Character> stack = new Stack<>();
Stack<Integer> num = new Stack<>();
num.push(0);
num.push(0);
int res=0;
int max=0;
for(int i = 0; i< s.length();i++){
char temp = s.charAt(i);
if(temp=='(') {
stack.push('(');
num.push(0);
}
else{
if(!stack.isEmpty()&&stack.peek()=='('){
res=2+num.pop()+num.peek();
num.pop();
num.push(res);
if(res>max) max=res;
stack.pop();
}
else{
stack.push(')');
num.push(0);
if(res>max) max=res;
res=0;
}
}
}
if(res>max) max=res;
return max;
}
}
第一个栈 stack记录括号的信息，匹配的话就抵消
第二栈 num记录加上当前的字符，最大的匹配数字。
image.png
image.png
遇到匹配的括号，nums最后两个数字出栈，求和加2后再入栈，
遇到‘（’或者不匹配的括号，加0.
stack遇到匹配的括号，‘（’出栈，遇到其他的或者不匹配之际进栈。
题解还有其他的解法，他们只用了一个栈，但是总体思路好像变幻不大：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
