32. Longest Valid Parentheses

stack O(n) time O(n) space
所有匹配的括号都出栈了，栈里剩下的都是匹配不上的，所以两个匹配不上的括号之间的就是匹配上的括号串，统计最长的可以匹配上的括号串的长度即可

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        vector<int> v{-1}; // 开始加入-1方便后面计算，比如"()()())"
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') { // 如果是"("，直接把下标入栈
                v.push_back(i);
            } else {
                if (v.back() != -1 && s[v.back()] == '(') { // 如果是")"，并且栈不为『空』或者栈顶是"("，证明有正确的匹配，将栈顶的"("的下标出栈
                    v.pop_back();
                } else { // 否则证明是一个孤立无法匹配的")"，将下标入栈
                    v.push_back(i);
                }
            }
        }
        v.push_back(n); // 最后入栈一个结尾长度下标，方便计算，比如")()()"
        int res = 0;
        for (int i = 1; i < v.size(); ++i) {
            res = max(res, v[i] - v[i - 1] - 1); // 只需要检查前后两个不匹配的括号之前的距离便可以找到最长的合法匹配的括号的长度
        }
        return res;
    }
};

进一步优化，不需要最后再扫一遍，每次找到一个合法匹配就可以直接更新res

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stk, res = [-1], 0
        for i, c in enumerate(s):
            if c == '(':
                stk.append(i)
            elif stk[-1] >= 0 and s[stk[-1]] == '(':
                stk.pop()
                res = max(res, i - stk[-1])
            else:
                stk.append(i)
        return res

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length(), res = 0;
        stack<int> stk{{-1}}; // 开始加入-1方便后面计算，比如"()()())"
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') { // 如果是"("，直接把下标入栈
                stk.push(i);
            } else if (stk.top() != -1 && s[stk.top()] == '(') { // 如果是")"，并且栈不为『空』或者栈顶是"("，证明有正确的匹配，将栈顶的"("的下标出栈
                stk.pop(); // 一定要先出栈再更新res
                res = max(res, i - stk.top()); // 当前是一个合法的匹配，更新res
            } else { // 否则证明是一个孤立无法匹配的")"，将下标入栈
                stk.push(i);
            }
        }
        return res;
    }
};