image.png
這道題一開始還是有點(diǎn)思路的恋博，可以用堆棧的方法來寫：
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;
}
}
第一個(gè)棧 stack記錄括號(hào)的信息齐佳，匹配的話就抵消
第二棧 num記錄加上當(dāng)前的字符，最大的匹配數(shù)字债沮。
image.png
image.png
遇到匹配的括號(hào)炼吴，nums最后兩個(gè)數(shù)字出棧，求和加2后再入棧疫衩，
遇到‘（’或者不匹配的括號(hào)硅蹦，加0.
stack遇到匹配的括號(hào)，‘（’出棧，遇到其他的或者不匹配之際進(jìn)棧童芹。
題解還有其他的解法涮瞻，他們只用了一個(gè)棧，但是總體思路好像變幻不大：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
