最长有效括号

Question

给定一个仅包含字符"("one_answers"("的字符串，查找最长有效(格式正确(圆括号子字符串的长度。

我已经实现了以下代码。

public int LongestValidParentheses(string s) {
if(String.IsNullOrEmpty(s)) return 0;
int longest = 0;
int tempLongest = 0;
bool lastValid = false;

Stack<char> stack = new Stack<char>();

for(int i = 0; i < s.Length; i++){
if(s[i] == '('){
stack.Push(s[i]);
if(!lastValid)
tempLongest = 0;
}
else{
if(stack.Count > 0){
stack.Pop();
tempLongest += 2;
lastValid = true;
}
}
longest = Math.Max(longest, tempLongest);
}

return longest;
}

它似乎适用于大多数情况；((("(((((("(((((((((("((((((((((">

获得"的错误输出；(((("；

我得到的结果：4

预期：2

有没有线索表明我在逻辑中遗漏了什么？我可以访问工作解决方案，但如果有人帮助我识别代码中的问题，我将不胜感激。

Answer 1

查看下面的代码是否适合您的预期输出。在您的代码中，没有检查重置lastValid标志以打破运行计数。我用不同的方式处理它。每当我们在有效期内遇到破损时，我们都可以从堆栈中删除一个项目。

代码：

public int LongestValidParentheses(string s)
{
if (String.IsNullOrEmpty(s)) 
return 0;
int longest = 0;
int tempLongest = 0;
bool lastValid = false;
Stack<char> stack = new Stack<char>();
int exprLen = s.Length;
for (int i = 0; i < exprLen; i++)
{
if (s[i] == '(')
{
stack.Push(s[i]);
//if (!lastValid)
//  tempLongest = 0;
}
else
{
if (stack.Count > 0)
{
stack.Pop();
tempLongest += 2;
if (stack.Count > 0)
{
//we are the end, but still if there is items on stack
//except if there is only a pair, deduct
if (tempLongest ==4 && (exprLen - i) == 1)
{
if (stack.Count == 1)
tempLongest -= 2;
}
//lastValid = true;
}
}
else
{
//lastValid = false;
if(stack.Count>0)
stack.Pop();
tempLongest = 0;
}
}
longest = Math.Max(longest, tempLongest);
}
return longest;
}

测试结果：parens(((((：2

parens(((：2

parens(((((：2

parens((：2

parens((：4

parens(((((

parens((((((((((：6