给定一个仅由 '(' 和 ')' 组成的字符串 S，找出最长有效子串的长度

Question

我知道在 Whosebug 上已经有关于此的问题，但我的代码不同。所以我使用堆栈来解决这个问题，但不知何故我的输出结果不正确，但是当我尝试使用给出错误输出的输入测试用例在纸上解决这个问题时，我能够得到正确的答案，我错过了什么代码或者哪里错了？

错误输出的测试用例 - ))))))()()))(())))())((()()()())(((()))( ))

我的输出 - 6，预期输出 - 20

我的代码-

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
    //code
    int tc,count,max;
    cin>>tc;
    while(tc--){
        string s;
        cin>>s;
        max = 0;
        count = 0;
        stack<char> store;
        int len = s.size();
        for(int i=0;i<len;i++){
            if(s[i] == '(') store.push(s[i]);
            else{
                if(!store.empty() && store.top() == '('){
                    count+= 2;
                    store.pop();
                }else if(count>max){
                    max = count;
                    count = 0;
                }
            }
        }
        cout<<max<<"\n";
    }
    return 0;
}

Answer 1

在这段代码中：

if(!store.empty() && store.top() == '(') {
     count+= 2;
     store.pop();
} else if(count>max) {
     max = count;
     count = 0;
}

考虑当最长的有效子字符串位于字符串末尾时会发生什么：您永远不会遇到错误分支，因此您永远不会更新 max。对代码的最小更改可能是：

if(!store.empty() && store.top() == '(') {
     count+= 2;
     store.pop();
     if(count>max) {
         max = count;
     }
} else {
     count = 0;
}

每次 count 更改时，您更新 max 的位置。

可以对代码进行更多的简化，例如由于 stack 仅包含相同的值，您可以将其替换为 int.

给定一个仅由 '(' 和 ')' 组成的字符串 S，找出最长有效子串的长度

Given a string S consisting only of '(' and ')', find out the length of the longest valid substring

c++

string

queue

stack

data-structures