最长有效括号（leetcode_32）

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

我自己的想法是，遍历一遍，每找到一个左括号，就通过栈的方式找到匹配的右括号，然后直接让遍历从找的的右括号的后一个开始。然后同时维持一个当前匹配的到最长的有效括号序列的长度，这个数字当序列不再有效的话变为0。

class Solution

{

public:

    int longestValidParentheses(string s)

    {

        if (s.empty() || s.find(')') == string ::npos || s.find('(') == string ::npos)

            return 0;



        int length = s.size();

        int right;

        int max_length = 0;

        int current_length = 0;



        for (int i = 0; i < length; ++i)

        {

            right = find_right(s, i, length);

            if (right != 0)

            {

                current_length += (right - i + 1);

                max_length = max_length > current_length ? max_length : current_length;

                i = right;

                continue;

            }



            current_length = 0;

        }

        return max_length;

    }



private:

    int find_right(string &s, int left, int &max_length)

    {

        if (s[left] == ')' || s.find(')', left) == string::npos)

            return 0;

        stack<char> my_stack;

        for (int i = left; i < max_length; ++i)

        {

            if (s[i] == ')')

                my_stack.pop();

            else

                my_stack.push('(');



            if (my_stack.empty())

                return i;

        }

        return 0;

    }

};

但是我的这个想法有个大问题，那就是如果出现极端情况，就是那种全部是左括号，然后没有右括号的情况，会每个逐次匹配，然后复杂度直接到O(N^2)。

现在我看一个大佬的写法，也是只扫描一遍，但是人家是同时维持到这个节点结束的最长有效匹配的序列，每次判断下一个是否成立时，之前判断当前点的之前最长有效序列的长度个点那个点是否和当前点匹配就行了。

class Solution {

public:

    int longestValidParentheses(string s) {

        int res = 0;

        vector<int> dp(s.size(), 0);



        for (int i = 1; i< s.size(); i++) {

            if (s[i] == ')'){

                if (s[i-1] == '('){

                    dp[i] = (i > 2? dp[i-2]: 0) + 2; 

                } else if (i-dp[i-1] > 0 && s[i-dp[i-1] - 1] == '(') {

                    dp[i] = dp[i-1] + ((i-dp[i-1]) >= 2? dp[i-dp[i-1]-2] : 0) + 2;

                }

                res = max(res, dp[i]);

            } 

        }

        return res;

    }

};