为何动态分配内存的最长回文子串解法占用更多RAM？

问题描述 #

在LeetCode解决最长回文子串问题时，我写了两个逻辑完全一致的解法：用静态分配内存的版本仅占用10MB RAM，而动态分配内存的版本却占用了244MB，请问这是什么原因？

代码对比 #

char * longestPalindrome(char * s){
    int n = strlen(s);
    int ps[n][n]; // 静态分配：栈内存
    // int *ps = (int *)malloc(n * n * sizeof(int)); // 动态分配：堆内存
    memset(ps, 0, sizeof(ps[0][0]) * n * n);
    int maxi = 0, maxj = 0;
    for (int i = 0; i < n; i++)
    {
        ps[i][i] = 1; // ps[i*n+i] = 1;
    }
    for (int l = 2; l <= n; l++)
    {
        for (int i = 0; i <= n - l; i++)
        {
            int j = i + l - 1;
            if (i == j - 1)
            {
                if (ps[i][j] = (s[i] == s[j])) // if (ps[i*n+j] = (s[i] == s[j]))
                {
                    maxi = i;
                    maxj = j;
                }
            }
            else
            {
                if (ps[i][j] = (s[i] == s[j] && ps[i + 1][j - 1])) // if (ps[i*n+j] = (s[i] == s[j] && ps[(i + 1)*n+(j - 1)]))
                {
                    maxi = i;
                    maxj = j;
                }
            }
        }
    }
    // free(ps); // 动态分配的释放逻辑
    char *p = &s[maxi];
    s[maxj + 1] = '\0';
    return p;
}

差异原因分析 #

1. 内存区域与管理开销

   • 静态数组ps[n][n]是在栈内存上分配的，栈内存由系统自动管理，分配的内存块连续紧凑，没有额外的管理元数据开销，而且栈的总大小通常限制在几MB级别，所以实际占用内存很低。
   • 动态分配的malloc是从堆内存申请空间，堆内存需要系统维护每个内存块的元数据（比如块大小、空闲链表指针等），这些元数据会占用额外内存；另外堆内存容易产生碎片化，可能导致系统为了满足申请，分配比实际需要更大的连续内存块，进一步拉高内存占用。

2. LeetCode的内存统计规则
   LeetCode的内存统计会把堆内存的所有消耗（包括管理元数据、碎片化带来的额外占用）全部计入程序的内存使用量，而栈内存属于进程的基础运行内存，通常不会被计入“程序额外占用的内存”，或者仅统计栈的峰值使用，而栈本身的大小限制决定了它的峰值不会很高。

3. 内存释放的时机影响

   • 栈内存会在函数执行完毕后立即自动释放，每个测试用例运行结束后，栈的占用都会清零，不会累积。
   • 堆内存需要手动调用free释放，如果测试框架在函数返回后才统一回收堆内存，或者多个测试用例连续运行时堆内存没有及时释放，会导致内存峰值被统计得更高，从而出现巨大的内存占用差异。

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