最长有效括号

题目

• 最长有效括号

方法一：dp

  int longestValidParentheses(string s) {
        int ans = 0;
        stack<int> sta;
        sta.push(-1);
        for(int i = 0;i < s.size();i ++)
        {
            if(s[i] == '(')sta.push(i);
            else{
                sta.pop();
                if(sta.empty())
                {
                    sta.push(i);
                }else{
                    ans = max(ans,i - sta.top());
                }
            }
        }
        return ans;
  }

方法二：栈

  int longestValidParentheses(string s) {
        s = ' ' + s;
        int n = s.size();
        vector<int> f(n,0);
        for(int i = 2;i < n;i ++)
        {
            if(s[i] == ')'){
                if(s[i-1] == '(')f[i] = f[i-2] + 2;
                else if(s[i - f[i-1] - 1] == '(')f[i] = f[i - f[i-1] - 2] + f[i-1] + 2;
            }

        }
        return *max_element(f.begin(),f.end());
    }

方法三：贪心

    int longestValidParentheses(string s) {
        int left = 0,right = 0;
        int ans = 0;
        for(int i = 0;i < s.size();i ++)
        {
            if(s[i] == '(')left ++;
            else right ++;

            if(left == right) ans = max(ans,left * 2);
            else if(right > left)right = left = 0;
        }
        left = 0,right = 0;
        for(int i = s.size() - 1;i >= 0;i --)
        {
            if(s[i] == '(')left ++;
            else right ++;

            if(left == right) ans = max(ans,left * 2);
            else if(right < left)right = left = 0;
        }
        return ans;
        
    }

相关题目

• https://codeforces.com/problemset/problem/5/C
• 方法和上面的方法三一摸一样
• 只需要再加上一个记录答案数量的变量即可

void solve() 
{
    string s;cin >> s;
    int maxLen = longestValidParentheses(s);

    int left = 0,right = 0;
    int maxNum = 1,num = 0;
    for(int i = 0;i < s.size();i ++)
    {
        if(s[i] == '(')left ++;
        else right ++;

        if(right > left)right = left = 0;
        else if(right == left && right*2 == maxLen)num ++;
    }
    maxNum = max(maxNum,num);
    // debug1(num);
    left = right = num = 0;
    for(int i = s.size() - 1;i >= 0;i --)
    {
        if(s[i] == '(')left ++;
        else right ++;

        if(right < left)right = left = 0;
        else if(right == left && right*2 == maxLen)num ++;
    }
    // debug1(num); 
    maxNum = max(maxNum,num);
    cout << maxLen << " " << maxNum << endl;
    
}