Codility括号挑战解决方案正确性达标但性能测试失败，求排查耗时点

我正在解决Codility的括号挑战，正确性测试已100%通过，但性能测试未能通过。我认为该解法的时间复杂度应为O(n)，想找出其中的耗时点。性能测试截图显示存在超时案例，得分截图显示部分性能测试未通过。

我的实现代码如下：

private class Solution
{
    private Stack<char> _stack = new Stack<char>();
    private HashSet<char> _visited = new HashSet<char>() { '}', ']', ')' };

    private Dictionary<char, char> _dictionary = new Dictionary<char, char>()
    {
        { '{', '}' },
        { '[', ']' },
        { '(', ')' }
    };

    public int solution(String S)
    {
        if (S.Length % 2 != 0)
        {
            return 0;
        }
        foreach (char c in S)
        {
            if (_stack.Count > 0)
            {
                var peek = _stack.Peek();
                Debug.WriteLine($"Peek: {peek} - char: {c}");
                if (GetOpposite(peek).Equals(c))
                {
                    Debug.WriteLine($"Pop {peek}");
                    _stack.Pop();
                }
                else
                {
                    if (_visited.Contains(c))
                        return 0;
                    Debug.WriteLine($"Push: {c}");
                    _stack.Push(c);
                }
            }
            else
            {
                if (_visited.Contains(c))
                    return 0;
                _stack.Push(c);
            }
        }

        return _stack.Count == 0 ? 1 : 0;
    }

    private char GetOpposite(char c)
    {
        return _dictionary[c];
    }
}

耗时点分析 #

1. Debug.WriteLine的IO开销：代码中大量使用Debug.WriteLine输出日志，IO操作的速度远慢于内存计算，在处理大长度字符串时，这些日志输出会导致严重的性能损耗，直接触发超时。
2. 成员变量的栈实例：_stack是类的成员变量，若多次调用solution方法会残留之前的状态（虽然正确性测试通过可能是因为每次新建实例），但局部变量的访问效率比成员变量更高，且更安全。
3. 哈希表的额外开销：使用HashSet和Dictionary来判断括号类型，对于仅3种括号的场景，哈希表的查找开销比直接的条件判断更高。

优化建议 #

• 立即移除所有Debug.WriteLine语句，消除IO性能瓶颈。
• 将_stack改为solution方法内的局部变量，避免状态残留并提升访问速度。
• 替换哈希表判断为直接的条件分支，比如用switch或if判断字符类型，减少哈希查找的开销。
• 优化逻辑：遇到左括号直接入栈，遇到右括号再检查栈顶是否匹配，减少不必要的分支判断。

优化后的示例代码 #

private class Solution
{
    public int solution(String S)
    {
        if (S.Length % 2 != 0)
        {
            return 0;
        }
        
        Stack<char> stack = new Stack<char>();
        
        foreach (char c in S)
        {
            switch (c)
            {
                case '{':
                case '[':
                case '(':
                    stack.Push(c);
                    break;
                case '}':
                    if (stack.Count == 0 || stack.Pop() != '{')
                        return 0;
                    break;
                case ']':
                    if (stack.Count == 0 || stack.Pop() != '[')
                        return 0;
                    break;
                case ')':
                    if (stack.Count == 0 || stack.Pop() != '(')
                        return 0;
                    break;
                default:
                    return 0;
            }
        }
        
        return stack.Count == 0 ? 1 : 0;
    }
}

内容的提问来源于stack exchange，提问作者GlebZ