一. 题目

二. 思路

1. dp

2. 栈

三. 代码

1. dp

class Solution
{
    static final int N = (int) 3e4 + 10;
    int[] f = new int[N];

    public int longestValidParentheses(String s)
    {
        int n = s.length(), ans = 0;
        for (int i = 1; i < n; ++i)
            if (s.charAt(i) == ')')
            {
                if (s.charAt(i - 1) == '(') f[i] = f[Math.max(0, i - 2)] + 2;
                else if (i - 1 - f[i - 1] >= 0 && s.charAt(i - 1 - f[i - 1]) == '(')
                    f[i] = f[Math.max(0, i - 1 - f[i - 1] - 1)] + f[i - 1] + 2;
                ans = Math.max(ans, f[i]);
            }
        return ans;
    }
}

2. 栈

class Solution
{
    Deque<Integer> stk = new ArrayDeque<>();

    public int longestValidParentheses(String s)
    {
        stk.clear();
        int n = s.length(), ans = 0;
        stk.offer(-1);
        for (int i = 0; i < n; ++i)
            if (s.charAt(i) == '(') stk.offer(i);
            else
            {
                stk.pollLast();
                if (stk.isEmpty()) stk.offer(i);
                else ans = Math.max(ans, i - stk.peekLast());
            }
        return ans;
    }
}