C#如何使用栈优化HackerRank Equal Stacks题解以解决超时问题

你代码的时间复杂度理论上是O(m+n+k)，符合题目要求，但是常数项过高是超时的核心原因：

• 你大量使用了LINQ的Any()方法判断栈/列表是否为空：虽然.NET中对应集合的Any()已经做了优化（优先判断Count），但LINQ方法的调用开销远高于直接读取原生Count属性，尤其在循环中反复调用时，累计开销会被放大到超出时间限制。
• 存在大量冗余的非空判断：比如循环条件已经保证三个栈都不为空，循环内部的LocalPeek里的非空判断完全多余，额外增加了调用开销。
• GetStack方法中每次通过LocalPeek取当前累加值，额外增加了方法调用和属性读取开销。

可直接落地的修改点： #

• 所有判断集合非空的逻辑，全部替换为读取Count > 0，移除所有Any()调用
• 移除冗余的LocalPeek、CountHeight、IsEmpty封装，直接操作集合原生方法减少调用开销
• 用临时变量存储累加值重构GetStack方法，省去反复读取栈顶的开销

优化后代码： #

public static int equalStacks(List<int> h1, List<int> h2, List<int> h3)
{
    if (h1.Count == 0 || h2.Count == 0 || h3.Count == 0) return 0;
    
    var h1Stack = GetStack(h1);
    var h2Stack = GetStack(h2);
    var h3Stack = GetStack(h3);
    
    while (h1Stack.Count > 0 && h2Stack.Count > 0 && h3Stack.Count > 0)
    {
        var h1Height = h1Stack.Peek();
        var h2Height = h2Stack.Peek();
        var h3Height = h3Stack.Peek();
    
        if (h1Height == h2Height && h1Height == h3Height) return h1Height;
        
        var max = Math.Max(h1Height, Math.Max(h2Height, h3Height));
        if (h1Height == max) h1Stack.Pop();
        if (h2Height == max) h2Stack.Pop();
        if (h3Height == max) h3Stack.Pop();
    }
    
    return 0;
}

static Stack<int> GetStack(List<int> numbers)
{
    var stack = new Stack<int>(numbers.Count);
    int sum = 0;
    for (var i = numbers.Count - 1; i >= 0; --i)
    {
        sum += numbers[i];
        stack.Push(sum);
    }
    return stack;
}

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