最长有效括号

Question

给定一个仅包含字符“(”和“)”的字符串，找到最长有效（格式良好）括号子字符串的长度。

我已经实现了以下代码。

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;
}

测试结果： 括号 ()(() : 2

括号 (() : 2

括号 ())))) : 2

括号 ((((() : 2

括号 ((((()() : 4

括号）（（）（）（（））：8

括号 ((())))))((( : 6

Answer 2

这是一种更好的方法，可以一次性解决 O(n) 问题

public class Solution {
public int longestValidParentheses(String s) {
    Stack<Integer> stack = new Stack<Integer>();
    int max=0;
    int left = -1;
    for(int j=0;j<s.length();j++){
        if(s.charAt(j)=='(') stack.push(j);            
        else {
            if (stack.isEmpty()) left=j;
            else{
                stack.pop();
                if(stack.isEmpty()) max=Math.max(max,j-left);
                else max=Math.max(max,j-stack.peek());
            }
        }
    }
    return max;
}

}