为什么在 LeetCode 中使用实例变量比局部变量需要更多内存？

Question

我试图在 LeetCode 上使用 DFS 解决图形问题。事实证明，使用实例变量比局部变量占用更多空间。

这是我的代码：

本地

class Solution {
public:
    
    void dfs(int node, int parent, int& counter, vector<int>& low, vector<int>& id_to_rank, vector<vector<int>>& edges, vector<vector<int>>& ans){

        id_to_rank[node] = counter;
        low[node] = counter;
        counter++;

        for (const auto& e : edges[node]){
            if (parent == e) continue;

            if (id_to_rank[e] == -1){
                dfs(e, node, counter, low, id_to_rank, edges, ans);
            
                low[node] = min(low[node], low[e]);

                if (low[e] > id_to_rank[node]){
                    ans.push_back({e, node});
                }
            }else{
                low[node] = min(low[node], low[e]);
            }

        }

        return;
    }

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> edges(n);
        vector<int> id_to_rank (n, -1);
        vector<int> low(n);

        vector<vector<int>> ans;
        int counter = 0;

        for (const auto& c : connections){
            edges[c[0]].push_back(c[1]);
            edges[c[1]].push_back(c[0]);

        }

        dfs(0, -1, counter, low, id_to_rank, edges, ans);

        return ans;
    }
};

实例

class Solution {
public:
    vector<vector<int>> ans;
    int counter = 0;

    void dfs(int node, int parent, vector<int>& low, vector<int>& id_to_rank, vector<vector<int>>& edges){

        id_to_rank[node] = counter;
        low[node] = counter;
        counter++;

        for (const auto& e : edges[node]){
            if (parent == e) continue;

            if (id_to_rank[e] == -1){
                dfs(e, node, counter, low, id_to_rank, edges, ans);
            
                low[node] = min(low[node], low[e]);

                if (low[e] > id_to_rank[node]){
                    ans.push_back({e, node});
                }
            }else{
                low[node] = min(low[node], low[e]);
            }

        }

        return;
    }

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> edges(n);
        vector<int> id_to_rank (n, -1);
        vector<int> low(n);

        for (const auto& c : connections){
            edges[c[0]].push_back(c[1]);
            edges[c[1]].push_back(c[0]);

        }

        dfs(0, -1, low, id_to_rank, edges);

        return ans;
    }
};

我已经多次重新提交了这两个解决方案，差异是恒定的（大约是内存的 10%）。我的猜测是 LeetCode 可能在每个测试用例上使用相同的对象，从而产生差异。但即便如此，我还是不知道到底发生了什么。

为什么在 LeetCode 中使用实例变量比局部变量需要更多内存？

（这是我第一次发布问题，所以如果有任何我没有遵守的规则，请告诉我）

Answer 1

return ans

在调用时返回成员变量

COPY

的

ans

，因此您需要该对象的双倍内存，

Solution sol; // has the vector
auto answer = sol.criticalConnections(...) // a copy is made

您可以将该成员移出。

return std::move(sol)


// the vector is moved into answer
auto answer = sol.criticalConnections(...) 
// after this line sol vector is empty

不幸的是，竞争性编码网站只教你竞争性编码，他们不教你编码，也不教你C++，你只能从一本合适的C++教科书

来学习C++