solution.md

# 最长有效括号

<p>给你一个只包含 <code>'('</code> 和 <code>')'</code> 的字符串，找出最长有效（格式正确且连续）括号子串的长度。</p><p> </p><div class="original__bRMd"><div><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>s = "(()"<strong><br />输出：</strong>2<strong><br />解释：</strong>最长有效括号子串是 "()"</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>s = ")()())"<strong><br />输出：</strong>4<strong><br />解释：</strong>最长有效括号子串是 "()()"</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>s = ""<strong><br />输出：</strong>0</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>0 <= s.length <= 3 * 10<sup>4</sup></code></li>	<li><code>s[i]</code> 为 <code>'('</code> 或 <code>')'</code></li></ul></div></div>
<p>以下<font color="red">错误</font>的选项是？</p>

## aop

### before

```cpp

```
### after

```cpp

```

## 答案

```cpp
class Solution
{
public:
    int longestValidParentheses(string s)
    {
        int n = s.size();
        if (n == 1)
            return 0;
        if (n == 2)
        {
            if (s[0] == '(' && s[1] == ')')
                return 2;
            else
                return 0;
        }

        vector<int> dp(n, 0);
        int max = 0;
        for (int i = 1; i < n; i++)
        {
            if (s[i] == ')' && s[i - 1] == '(' && i >= 2)
                dp[i] = dp[i - 2] + 2;
            if (s[i] == ')' && s[i - 1] == '(' && i == 1)
                dp[i] = 2;
            if (s[i] == ')' && s[i - 1] == ')' && s[i - dp[i - 1] - 1] == '(')
                dp[i] = dp[i - 1] + 2 + dp[dp[i - 1] - 2];
            if (dp[i] > max)
                max = dp[i];
        }
        return max;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    int longestValidParentheses(string s)
    {
        stack<int> stk;
        int invalid = -1;
        int len = 0, max_len = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '(')
            {
                stk.push(i);
            }
            else
            {
                if (stk.empty())
                {
                    invalid = i;
                }
                else
                {
                    stk.pop();
                    if (stk.empty())
                    {
                        max_len = max(i - invalid, max_len);
                    }
                    else
                    {
                        max_len = max(i - stk.top(), max_len);
                    }
                }
            }
        }
        return max_len;
    }
};
```

### B

```cpp
class Solution
{
public:
    int longestValidParentheses(string s)
    {
        stack<int> left;
        left.push(-1);
        int size = 0, maxSize = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '(')
                left.push(i);
            else
            {
                if (left.size() != 1)
                {
                    left.pop();
                    size = i - left.top();
                    maxSize = max(maxSize, size);
                }
                else
                {
                    left.pop();
                    left.push(i);
                }
            }
        }
        maxSize = max(maxSize, size);
        return maxSize;
    }
};
```

### C

```cpp
class Solution
{
public:
    int longestValidParentheses(string s)
    {
        queue<pair<int, int>> q;
        bool *valid = new bool[s.length() + 1];
        int imax = -1;
        memset(valid, 0, sizeof(bool) * (s.length() + 1));
        for (int i = 0; i < int(s.length()) - 1; i++)
        {
            if (s[i] == '(' && s[i + 1] == ')')
            {
                valid[i] = true;
                valid[i + 1] = true;
                q.push(make_pair(i, i + 1));
            }
        }
        while (!q.empty())
        {
            pair<int, int> parentheses;
            parentheses = q.front();
            q.pop();
            int l = parentheses.first, r = parentheses.second;
            while (l >= 0 && valid[l])
                l--;
            while (r < s.length() && valid[r])
                r++;
            if (!valid[l] && !valid[r])
            {
                if (s[l] == '(' && s[r] == ')')
                {
                    valid[l] = true;
                    valid[r] = true;
                    q.push(make_pair(l, r));
                }
                else
                {
                    l = l + 1;
                    r = r - 1;
                }
            }
            if (r - l > imax)
                imax = r - l;
        }
        return imax + 1;
    }
};

```