LeetCode验证二叉树前序序列化：为什么我的简洁C++解法比0ms样例慢？

这是2021年8月26日的LeetCode题目。我提交了多份解法，其中表现最优的一份运行耗时为7ms，但当我看到0ms的样例解法时十分意外：该解法逻辑更复杂，包含大量条件判断语句。

题目描述（已编辑） #

给定逗号分隔的字符串preorder，判断它是否是二叉树正确的前序遍历序列化结果，返回true或false。
输入保证字符串中每个逗号分隔的值要么是整数，要么是代表空指针的字符'#'。

我曾在LeetCode讨论区提问但未得到回应，因此在此咨询：

我的解法（耗时7ms） #

class Solution
{
public:
    bool isValidSerialization(string preorder)
    {
        int c = 1;
        const int L = preorder.length();
        bool state = true;
        for (int i = 0; i < L; i++)
        {
            if (state)
            {
                state = false;
                if (!c)
                    return false;
                if (preorder[i] != '#')
                    c++;
                else
                    c--;
            }
            else
                state = preorder[i] == ',';
        }
        return !c;
    }
};

0ms样例解法 #

class Solution {
public:
    bool isValidSerialization(string pre) {
        stack<int> s;
        if(pre.length()==1 && pre[0]=='#'){
            return true;
        }
        string num = "";
        for(int i=0; i<pre.length(); i++){
            if(pre[i]==','){
                continue;
            }
            if(s.empty() && i>0){
                return false;
            }
            if(pre[i]=='#'){
                if(s.empty()){return false;}
                s.top()--;
                while(!s.empty() && s.top()==0){
                    s.pop();
                    if(!s.empty()){s.top()--;}
                    if(!s.empty() && s.top()<0){
                        return false;
                    }
                }
            }
            else{
                int j=i;
                while(j<pre.size() && pre[j]!=','){
                    j++;
                }
                i = j-1;
                s.push(2);
            }
            //cout << i << " -> " << s.size() << endl; 
        }
        if(s.size()>0){
            //cout << s.size() << endl;
            return false;
        }
        return true;
    }
};

我的疑问 #

我的解法没有使用stack等复杂数据结构，条件判断语句数量也远少于样例解法，为什么运行速度反而更慢？

原因说明 #

• LeetCode的运行计时本身存在一定波动，同一份代码多次提交耗时可能在0~10ms区间浮动，7ms和0ms的差距并不完全代表代码的真实性能差距。
• 你的代码是逐字符遍历整个字符串，每个字符都需要走一次分支判断，哪怕是逗号、多位数的后续字符也要触发一次状态判断，遇到长数字时外层循环会执行更多次。而0ms解法遇到逗号直接跳过，遇到多位数时会直接跳转下标到当前数字的末尾，大幅减少了外层循环的执行次数，整体循环开销更低。
• 0ms解法有更多提前剪枝的逻辑，遇到非法输入时会更早返回结果，不需要遍历完整个字符串，对于大量非法测试用例的场景运行速度更快。
• std::stack的底层默认用deque实现，push、pop、取栈顶的操作都是O(1)时间复杂度，开销极低，远低于多轮循环判断带来的性能损耗。

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