优化C语言循环：解决LeetCode相邻重复字符删除超时问题

原代码的问题分析 #

你的代码采用多次循环扫描+字符串复制的逻辑，每次仅能消除一轮相邻重复项，比如处理abba时，第一次扫描会得到aa，还需要第二轮扫描才能完全清空。这种方式的时间复杂度为O(n²)，当字符串长度达到10^5时，重复的扫描、字符串复制和内存清空操作会直接导致超时。

另外，每次循环中调用的strlen(s)、strcpy(s,res)、memset(res, '\0', sizeof res)函数，在处理大字符串时会产生极大的额外开销，进一步拖慢执行速度。

优化方案：原地栈模拟 #

用数组模拟栈的思路，只需一次遍历就能完成所有重复项的消除，时间复杂度降至O(n)，且可以实现原地修改，大幅降低内存开销。

核心逻辑：

• 用指针top标记栈顶位置（初始为-1，表示空栈）
• 遍历原字符串的每个字符：
  • 若栈不为空，且当前字符与栈顶字符相同，则弹出栈顶（top--）
  • 否则，将当前字符压入栈（top++，将字符存入栈对应位置）
• 最后在栈顶的下一个位置添加字符串结束符'\0'，直接返回原字符串

优化后的代码 #

char * removeDuplicates(char * s){
    int n = strlen(s);
    int top = -1; // 栈顶索引，初始为-1表示空栈
    for (int i = 0; i < n; i++) {
        if (top == -1 || s[top] != s[i]) {
            // 栈空或当前字符与栈顶不同，压入栈
            top++;
            s[top] = s[i];
        } else {
            // 当前字符与栈顶重复，弹出栈顶
            top--;
        }
    }
    s[top + 1] = '\0'; // 添加字符串结束符
    return s;
}

代码说明 #

1. 原地修改：直接在原字符串上模拟栈，无需额外数组和复制操作，彻底消除了strcpy、memset带来的开销。
2. 一次遍历：每个字符仅被处理一次，完全适配10^5长度的字符串场景。
3. 自动处理嵌套重复：比如abba这类嵌套重复的情况，遍历过程中会先消除bb得到aa，接着自动消除aa，一次遍历即可完成所有操作。

额外适配方案 #

如果题目不允许修改原字符串，可以创建一个独立的栈数组存储结果，最后将栈中字符复制到新字符串返回，逻辑与上述一致，仅需额外的O(n)空间，时间复杂度仍为O(n)。

内容的提问来源于stack exchange，提问作者Rafael Carro Gaudim