C++基于STL栈实现O(n)移除连续重复数字超时问题求解

• 第一版代码核心问题：
  每插入一个元素就执行tmp_st = st复制整个栈，单步操作耗时和当前栈长度正相关，最坏场景下总时间复杂度达到O(n²)，必然触发超时；同时逻辑仅判断连续重复长度恰好等于3的情况，遇到长度大于3的连续重复段（比如示例2消除2之后剩余的4个连续3）无法正确处理。
• 第二版代码核心问题：
  用独立全局变量n记录当前连续重复长度，没有和栈内元素绑定，消除元素后前后段拼接的计数回溯逻辑存在大量边界漏洞，计数错误率高；额外引入的tmp_st弹栈判断逻辑在多层连续消除场景下存在冗余操作，无法保证严格O(n)的时间复杂度。

核心是用双栈同步记录的方案，从根源上避免栈复制、全栈遍历的冗余操作：

• 维护两个栈：第一个栈存储实际的序列元素，第二个栈和元素栈一一对应，存储每个位置结尾的连续相同元素的累计长度，两个栈的压入、弹出操作完全同步。
• 处理每个输入元素时遵循以下规则：
  1. 元素栈为空时，直接将当前元素压入元素栈，计数1压入计数栈。
  2. 当前元素和元素栈顶元素相等时，元素压栈，计数栈压入「当前计数栈顶值+1」。
  3. 当前元素和栈顶元素不相等时，先检查计数栈顶值是否≥3：如果满足，说明栈顶这段连续元素可以消除，直接弹出对应数量的元素和计数，把消除长度累加到总移除数；消除完成后可能出现新的栈顶和当前元素相等的情况，重复检查直到栈顶不存在可消除段，再把当前元素按规则压栈。
  4. 每次元素压栈完成后，都要检查最新的栈顶计数是否≥3，及时处理新生成的可消除段（比如消除中间段后前后同值元素拼接成长度≥3的连续段）。
• 所有输入元素遍历完成后，最后检查一次栈内剩余的可消除段，处理完成后得到的总移除数就是最终结果。

该方案下每个元素最多只会经历1次压栈、1次弹栈，没有任何全栈复制、全栈遍历操作，总操作次数和输入长度线性相关，严格满足O(n)时间复杂度要求。

#include <cstdio>
#include <stack>
int main()
{
    int x, res = 0;
    std::stack<int> elem_st;  // 存储序列元素
    std::stack<int> cnt_st;   // 同步存储对应位置结尾的连续相同元素长度
    scanf("%d", &x);
    while (x != -1) {
        // 先处理栈顶已存在的可消除段
        while (!cnt_st.empty() && cnt_st.top() >= 3) {
            int remove_cnt = cnt_st.top();
            res += remove_cnt;
            for (int i = 0; i < remove_cnt; ++i) {
                elem_st.pop();
                cnt_st.pop();
            }
        }
        // 压入当前元素
        if (elem_st.empty()) {
            elem_st.push(x);
            cnt_st.push(1);
        } else if (x == elem_st.top()) {
            elem_st.push(x);
            cnt_st.push(cnt_st.top() + 1);
        } else {
            elem_st.push(x);
            cnt_st.push(1);
        }
        scanf("%d", &x);
    }
    // 遍历结束后处理栈内剩余的可消除段
    while (!cnt_st.empty() && cnt_st.top() >= 3) {
        int remove_cnt = cnt_st.top();
        res += remove_cnt;
        for (int i = 0; i < remove_cnt; ++i) {
            elem_st.pop();
            cnt_st.pop();
        }
    }
    printf("%d", res);
    return 0;
}

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