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/