C++ 超出内存限制但在 Python 中则不然

Question

我正在研究问题 1249。 LeetCode 上最少删除以形成有效括号。这是一个简单的问题，我可以用 C++ 和 Python 中的堆栈来解决。但是，我的 C++ 版本代码导致超出内存限制，而我的完全相同的 Python 代码仅消耗 15.3 MB 内存。谁能帮助我理解出了什么问题吗？

C++代码：

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<pair<char, int>> stack;
        for (int i=0; i<s.size();i++){
            if (s[i]!='(' && s[i]!=')')
                continue;
            else{
                if (!(stack.empty()) && stack.top().first=='(' && s[i]==')')
                    stack.pop();
                else
                    stack.push({s[i],i});
            } 
        }
        string res;
        for (int i=s.size()-1; i>=0;i--){ 
            if (!stack.empty() && i==stack.top().second)
                stack.pop();
            else{
                res = s[i] + res;
            }
        }
        return res;
            
    }
};

即使将C++中的堆栈数据结构替换为向量，仍然会导致超出内存限制。

Python3

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []
        for i, c in enumerate(s):
            if c!="(" and c!=")":
                continue
            if stack and stack[-1][0] == '(' and c==")":
                stack.pop()
            else:
                stack.append([c,i])
        
        res =""
        for i in range(len(s)-1,-1,-1):
            if stack and i == stack[-1][1]:
                stack.pop()
            else:
                res = s[i] + res
        return res

Answer 1

这是关于什么可以减少内存占用的另一种猜测。

我猜想每个 res = s[i] + res; 可能会重复重新分配内存，导致 res 过度分配超过所需的内存。

下面的代码（我希望）进行的分配要少得多，每个分配的大小都是当时所需的精确大小：

class Solution {
public:
    std::string minRemoveToMakeValid(std::string s) {
        std::stack<std::pair<char, int>> stack;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != '(' && s[i] != ')')
                continue;
            else {
                if (!(stack.empty()) && stack.top().first == '(' && s[i] == ')')
                    stack.pop();
                else
                    stack.push({ s[i],i });
            }
        }
        std::string res(s.size(),' ');
        auto iter{ s.size() };
        for (int i = s.size() - 1; i >= 0; i--) {
            if (!stack.empty() && i == stack.top().second)
                stack.pop();
            else {
                //res = s[i] + res;
                res[--iter] = s[i];
            }
        }
        return res.substr(iter);

    }
};